从递归到 DP：我是怎么把打家劫舍写对的
这道198. 打家劫舍 算是动态规划的“入门必修课”了。虽然题目说得挺刺激（我要去偷东西了），但其实逻辑非常严谨。
我做这道题的时候，最大的误区就是“贪心思维” —— 以为挑钱多的拿就行，结果直接翻车。
🟢 题目速览
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。
示例：
输入：[1,2,3,1] 输出：4 解释：偷 nums[0] + nums[2] = 1 + 3 = 4🧠 我的第一反应（贪心陷阱）
刚看到题，我心想这还不简单？
“那我肯定是尽量偷大的啊！”
比如[2, 1, 1, 2]，我第一反应是直接拿两个 2，加起来是 4。
但这明显错了，因为两个 2 是相邻的，报警器会响。
结论：
这不是一道“挑最大数”的题，而是一道“取舍”的题。
🚀 真正的进阶：状态定义
冷静下来想，对于第i个房间，我只有两种选择：
偷：那我就不能偷第
i-1个，收益是nums[i] + dp[i-2]不偷：那我就可以继承第
i-1个的收益，也就是dp[i-1]
所以状态转移方程就出来了：
dp[i] = Math.max(dp[i-1], nums[i] + dp[i-2])✅ 最终代码（滚动数组优化）
虽然可以用数组，但我面试时更喜欢写滚动变量（省空间，也显得熟练）。
class Solution { public int rob(int[] nums) { int n = nums.length; if (n == 0) return 0; if (n == 1) return nums[0]; int first = 0; // dp[i-2] int second = 0; // dp[i-1] for (int i = 0; i < n; i++) { int temp = second; // 暂存 dp[i-1] second = Math.max(second, first + nums[i]); first = temp; } return second; } }🔍 执行过程拆解（nums = [1,2,3,1]）
i | nums[i] | first (dp[i-2]) | second (dp[i-1]) | 计算过程 | 当前最优 |
|---|---|---|---|---|---|
0 | 1 | 0 | 0 | max(0, 0+1) | 1 |
1 | 2 | 0 | 1 | max(1, 0+2) | 2 |
2 | 3 | 1 | 2 | max(2, 1+3) | 4 |
3 | 1 | 2 | 4 | max(4, 2+1) | 4 |
✅ 最终返回 4。
🎯 我踩过的坑
边界没处理好
一开始忘了
n == 0或n == 1的情况，直接报错。
变量顺序写反
必须先存
second，再更新，否则first就被覆盖了。
误以为是贪心
千万别直接选最大的，要看“能不能选”。
🧩 一句话总结
打家劫舍的本质是“选或不选” 的博弈。
对于当前房子，要么偷（加上上上个的最大值），要么不偷（继承上一个的最大值）。
🎤 面试收尾（建议直接背）
“这道题是典型的线性 DP。
定义
dp[i]为前i个房屋能偷到的最大金额。对于第
i个房间，如果偷，就不能偷i-1，所以是nums[i] + dp[i-2]；如果不偷，就是dp[i-1]。为了优化空间，我使用了滚动变量来代替数组。”