数组一拉开，最容易写歪的动态规划题里，打家劫舍算一个。
不少人第一眼就想着“哪个数大抢哪个”，结果代码一跑，前后相邻房子不能同时偷这个限制，马上把贪心打碎。比如 [2,7,9,3,1]，你光盯着大的看，思路很容易拧巴。这个题我一般不先画表，先把选择关系掰明白：走到第 i 个房子时，其实只有两条路——要么不抢它，沿用前一个位置的最优解；要么抢它，那前一个房子就必须放弃，只能接上 i-2 的结果。
这题的味道，和线上很多“当前位置能不能做”很像。不是看当前值大不大，而是看“拿当前”之后，会不会把前面的选择链打断。这个判断顺序不理顺，后面代码容易写成一锅。
定义 dp[i] 表示考虑下标 0~i 这些房子，能偷到的最大金额。那转移就很直接：
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
翻译成人话就是：
- 偷第
i 家，那就不能偷第 i-1 家，只能接上 i-2 的最优结果。
边界别写飘了，这种题很多人不是不会，都是死在下标上。
我自己会先写个最直白的版本，把状态转移跑通，再看有没有必要压缩空间。先上正常写法：
publicclassHouseRobber{publicintrob(int[] nums){if (nums == null || nums.length == 0) {return0; }int n = nums.length;if (n == 1) {return nums[0]; }int[] dp = newint[n]; dp[0] = nums[0]; dp[1] = Math.max(nums[0], nums[1]);for (int i = 2; i < n; i++) {int skipCurrent = dp[i - 1];int takeCurrent = dp[i - 2] + nums[i]; dp[i] = Math.max(skipCurrent, takeCurrent); }return dp[n - 1]; }publicstaticvoidmain(String[] args){ HouseRobber solver = new HouseRobber(); System.out.println(solver.rob(newint[]{1, 2, 3, 1})); // 4 System.out.println(solver.rob(newint[]{2, 7, 9, 3, 1})); // 12 }}
拿 [2,7,9,3,1] 过一遍更清楚：
- 到
9，要么保留前面的 7，要么拿 2 + 9 = 11，取 11 - 到
3，要么保留 11，要么拿 7 + 3 = 10，还是 11 - 到
1，要么保留 11，要么拿 11 + 1 = 12，最终 12
这题还有个很适合面试里顺手优化的点：dp[i] 只依赖前两个状态，整个数组其实没必要留着。真在线上写业务代码，我也更偏向这种，小一点，干净一点。
publicclassHouseRobberOptimized{publicintrob(int[] nums){if (nums == null || nums.length == 0) {return0; }int prevTwo = 0;int prevOne = 0;for (int money : nums) {int current = Math.max(prevOne, prevTwo + money); prevTwo = prevOne; prevOne = current; }return prevOne; }}
这里的 prevTwo 可以理解成 dp[i-2]，prevOne 就是 dp[i-1]。每扫一个房子，更新一次当前最优解。
这题其实不难，难的是很多人一看到“不能选相邻”就慌，开始在那硬枚举。真没必要。凡是这种“当前位置选或不选”的题，八成都该往动态规划上靠。先别急着背公式，先盯住那句最关键的话：抢当前，就放弃前一个；不抢当前，就继承前一个。
