LeetCode 198 打家劫舍错误思路与纠错记录

本文仅仅用于记录本人在做这道算法题时的卡住的思路以及后续想明白后纠正的想法

在198. 打家劫舍 - 力扣（LeetCode）中，状态转移方程为：

# nums为原始的数据
dp[0] = 0
dp[1] = nums[0]
dp[i] = max(dp[i-1],dp[i-2]+nums[i-1])

dp[i]的意思是前i个房间（含第i个）所能够偷到的最大的金额，并且这个递推公式中隐含了dp[i-1]是偷了上一个房间的金额的，所以在这种情况下，dp[i]的值不能由dp[i-1]+nums[i-1]得到。

疑惑

为什么dp[i-1]的值一定是偷了第i-1个房间的呢，如果没有偷呢，那dp[i]的递推公式中的dp[i-1]不就应该可以写为dp[i-1]+nums[i-1]了吗，此时dp[i]的结果都可能不一样了。

纠错

假设一：dp[i-1]的确是没有偷第i间房间的

此时递推公式确实可以写为：

dp[i] = max(dp[i-1]+nums[i-1],dp[i-2]+nums[i-1])

但是既然第i-1间房间是没有被偷的，那么dp[i-1]和dp[i-2]本质上不就是相等的吗，因为dp[i-2]是前i-2间房所能偷到的最大的金额，而第i-1间我们又假设没有被偷的情况下能够取得到此时的最大金额，那么就有dp[i-2] = dp[i-1]，那么原来的递推公式：

dp[i] = max(dp[i-1],dp[i-2]+nums[i-1])
# 可以写为
dp[i] = max(dp[i-2],dp[i-2]+nums[i-1])

因此在这种情况下递推公式实际上是成立的

假设二：dp[i-1]是偷了第i间房间的

那么递推公式自然成立

综上：无论dp[i-1]是否是偷了第i-1间房屋的，递推公式都是成立的

最后

总结一下采用动态规划时需要满足的三个条件：

• 重复子问题：某个子问题（状态）会被多次访问
• 最优子结构：大问题的最优解由子问题的最优解拼成
• 无后效性：即当前状态下的决策仅仅与当前状态相关，与怎么到达这一个状态无关