企业官网建设流程全解析

LeetCode 198：打家劫舍

一、题目描述

今天做的是 LeetCode 198：打家劫舍。

题目大意是：

有一排房屋，每间房屋里都有一定金额的钱。小偷不能偷相邻的两间房屋，否则会触发报警。

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。

核心限制就是：

不能选择相邻的两个房屋。

二、第一版：我一开始想到的是“奇偶位置分别累加”

刚开始看到这道题的时候，我想到了一种比较直观的方法：

既然不能偷相邻的房屋，那么是不是可以把房屋分成：

偶数位置： 0、2、4、6…… 奇数位置： 1、3、5、7……

然后分别计算两组的总金额，最后取较大的那个。

所以我写出了：

classSolution{publicintrob(int[]nums){if(nums.length==1){returnnums[0];}elseif(nums.length==2){returnMath.max(nums[0],nums[1]);}int[]res=newint[2];res[0]=nums[0];res[1]=nums[1];for(inti=2;i<nums.length;i++){if(i%2==0){res[0]+=nums[i];}else{res[1]+=nums[i];}}returnMath.max(res[0],res[1]);}}

当时的想法是：

偶数位置全部偷 vs 奇数位置全部偷

然后选择金额更大的那一组。

看起来似乎符合“不偷相邻房屋”的要求。

但是提交之后：

40 / 70

直接出现了错误。

三、反例：[2,1,1,2]

官方给出的反例是：

nums = [2,1,1,2]

我的代码计算：

偶数位置： 2 + 1 = 3 奇数位置： 1 + 2 = 3

所以得到：

3

但是正确答案是：

4

因为真正最优的选择是：

2、1、1、2 ↑ ↑ 偷第 0 间和第 3 间

得到：

2 + 2 = 4

这里就暴露出了我第一版代码的问题：

不能偷相邻房屋，并不代表只能选择全部奇数位置或者全部偶数位置。

实际上，每一间房屋都存在“偷”或者“不偷”两种选择。

例如：

[2,1,1,2]

最优方案是：

偷 2 不偷 1 不偷 1 偷 2

所以：

2 + 2 = 4

这让我意识到：

我之前把“不能偷相邻房屋”理解得过于简单了。

四、重新思考：走到第 i 间房屋时应该怎么办？

发现第一种思路不对以后，我开始从每一间房屋重新考虑。

假设现在来到第i间房屋。

其实只有两种选择：

选择一：不偷第 i 间

那么目前能够获得的最大金额，就是：

前 i-1 间房屋能够获得的最大金额

也就是：

res[i-1]

选择二：偷第 i 间

既然偷了第i间，那么第i-1间就不能偷。

所以：

第 i 间的金额 + 前 i-2 间能够获得的最大金额

也就是：

res[i-2]+nums[i]

那么第i间处理完之后，最优答案就是这两个方案中较大的一个：

不偷 i： res[i-1] 偷 i： res[i-2] + nums[i]

因此得到状态转移：

res[i]=Math.max(res[i-1],res[i-2]+nums[i]);

这就是这道题最核心的一行代码。

五、第二版：开始真正使用 DP

于是我把代码修改成：

classSolution{publicintrob(int[]nums){if(nums.length==1){returnnums[0];}if(nums.length==2){returnMath.max(nums[0],nums[1]);}// dpint[]res=newint[nums.length];res[0]=nums[0];res[1]=Math.max(nums[0],nums[1]);for(inti=2;i<nums.length;i++){res[i]=Math.max(res[i-1],res[i-2]+nums[i]);}returnMath.max(res[nums.length-1],res[nums.length-2]);}}

这次的res[i]和第一版完全不同。

第一版的：

res[0]res[1]

只是用来保存：

偶数位置的总和 奇数位置的总和

而第二版中：

res[i]

表示：

考虑前i + 1间房屋时，能够偷到的最大金额。

这其实就是动态规划中非常重要的一步：

先明确dp[i]到底表示什么，再去推导状态转移。

六、用 [2,1,1,2] 看一下 DP 是怎么计算的

对于：

nums = [2,1,1,2]

初始化：

res[0] = 2

表示：

只有第 0 间房屋时，最多偷 2。

然后：

res[1] = max(2,1) = 2

表示：

前两间房屋最多偷 2。

来到第 2 间：

res[2] = max( res[1], res[0] + nums[2] )

也就是：

max( 2, 2 + 1 ) = 3

所以：

res[2] = 3

最后来到第 3 间：

res[3] = max( res[2], res[1] + nums[3] )

也就是：

max( 3, 2 + 2 ) = 4

最终：

res = [2,2,3,4]

答案就是：

4

这次就能够正确处理第一版无法处理的情况。

七、这次让我真正理解了 DP 的地方

以前看到动态规划的时候，很容易把注意力放在：

“dp 数组怎么写？”

但这道题让我感觉更重要的是：

dp[i]到底代表什么？

这里：

res[i]

不是：

偷第 i 间房屋能够获得多少钱

也不是：

前 i 间房屋全部偷掉的金额

而是：

考虑到第 i 间房屋为止，能够获得的最大金额。

一旦这个定义明确了，状态转移其实就比较自然：

第 i 间不偷 → res[i-1] 第 i 间偷 → res[i-2] + nums[i] 两者取最大值 → res[i]

也就是：

res[i]=Math.max(res[i-1],res[i-2]+nums[i]);

十、总结

这道题我第一次提交的时候，其实犯了一个比较典型的错误：

把“不能偷相邻房屋”简单理解成了“奇数位置和偶数位置二选一”。

但是实际情况是，每一间房屋都可以选择：

偷 或者 不偷

最优方案并不一定是完整的奇数位置或者完整的偶数位置。

例如：

[2,1,1,2]

最优方案就是：

偷第 0 间 不偷第 1 间 不偷第 2 间 偷第 3 间

因此需要记录：

到当前位置为止，能够获得的最大金额。

最终得到：

res[i]=Math.max(res[i-1],res[i-2]+nums[i]);

这次最大的收获是，我开始感觉到动态规划并不是：

“背一个 DP 公式。”

而是：

明确状态 ↓ 分析当前选择 ↓ 找到之前已经计算过的状态 ↓ 写出状态转移

这道题的状态其实非常简单：

dp[i] = 前 i+1 间房屋能够获得的最大金额

而每次只有两种选择：

不偷当前房屋 → dp[i-1] 偷当前房屋 → dp[i-2] + nums[i]

最后取最大值。

从第一版的错误思路，到第二版完整的 DP，我觉得这道题真正值得记录的不是代码本身，而是：

当一个“看起来合理”的贪心式思路被反例推翻以后，要学会重新定义问题的状态，而不是继续在原来的思路上打补丁。