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.length1){returnnums[0];}elseif(nums.length2){returnMath.max(nums[0],nums[1]);}int[]resnewint[2];res[0]nums[0];res[1]nums[1];for(inti2;inums.length;i){if(i%20){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.length1){returnnums[0];}if(nums.length2){returnMath.max(nums[0],nums[1]);}// dpint[]resnewint[nums.length];res[0]nums[0];res[1]Math.max(nums[0],nums[1]);for(inti2;inums.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] 前 i1 间房屋能够获得的最大金额而每次只有两种选择不偷当前房屋 → dp[i-1] 偷当前房屋 → dp[i-2] nums[i]最后取最大值。从第一版的错误思路到第二版完整的 DP我觉得这道题真正值得记录的不是代码本身而是当一个“看起来合理”的贪心式思路被反例推翻以后要学会重新定义问题的状态而不是继续在原来的思路上打补丁。
尧图网络