这道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]inums[i]first (dp[i-2])second (dp[i-1])计算过程当前最优0100max(0, 01)11201max(1, 02)22312max(2, 13)43124max(4, 21)4✅ 最终返回 4。 我踩过的坑边界没处理好一开始忘了n 0或n 1的情况直接报错。变量顺序写反必须先存second再更新否则first就被覆盖了。误以为是贪心千万别直接选最大的要看“能不能选”。 一句话总结打家劫舍的本质是“选或不选” 的博弈。对于当前房子要么偷加上上上个的最大值要么不偷继承上一个的最大值。 面试收尾建议直接背“这道题是典型的线性 DP。定义dp[i]为前i个房屋能偷到的最大金额。对于第i个房间如果偷就不能偷i-1所以是nums[i] dp[i-2]如果不偷就是dp[i-1]。为了优化空间我使用了滚动变量来代替数组。”
