#198
中等
低频
动态规划打家劫舍
这是一道围绕数组展开的高频练习。建议先掌握「动态规划」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
数组
题目分析
有一排房屋，每间房里有一定金额。
如果你偷了相邻的两间房，就会触发警报。要求你在不触发警报的前提下，偷到最多的钱。
一句话概括：
每到一个位置，都要在“偷当前房子”和“不偷当前房子”之间做选择。
接下来怎么看推荐代码： 带着这个理解再看推荐代码时，重点观察这条主线：遍历每间房时，只维护“偷到上一家为止”和“偷到上两家为止”的最优收益。
推荐代码
推荐解法：动态规划
时间复杂度： O(n)
空间复杂度： O(1)
核心思路： 遍历每间房时，只维护“偷到上一家为止”和“偷到上两家为止”的最优收益。
class Solution {
public int rob(int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
if (n == 1) {
return nums[0];
}
int[] dp = new int[n];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < n; i++) {
dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
}
return dp[n-1];
}
}结构化讲解
面试时怎么讲
开场思路
这题是经典的一维 DP。每间房只在“偷”或“不偷”之间做选择。
核心过程
- 定义状态表示考虑到当前位置时能获得的最大收益。
- 如果偷当前房，就接上前两间房的最优值；如果不偷，就沿用前一间房的最优值。
- 因此转移是
max(prev1, prev2 + nums[i])。 - 因为只依赖前两个状态，所以可以用滚动变量把空间压到
O(1)。
复杂度总结
时间复杂度 O(n)，空间复杂度 O(1)。
面试补一句：这题最值得记住的是“偷当前房就必须跳过上一房”。
核心思路
打家劫舍的限制是相邻房屋不能同晚偷，所以每一间房只有两个选择：偷它并接上前两家的最优值，或者不偷它沿用前一家的最优值。
步骤讲解
1
把问题转成前缀最优
设状态表示“考虑到当前位置时，最多能偷多少钱”。
为什么这样做：当前决策只依赖前一间和前两间的最优结果，适合做线性 DP。
对应代码提示：curr = Math.max(prev1, prev2 + num);
2
每间房都在偷和不偷之间二选一
如果偷当前房子，就只能接 prev2 + nums[i]；如果不偷，就保留 prev1。
为什么这样做：相邻房屋不能同时偷，约束决定了状态转移形式。
对应代码提示：int next = Math.max(prev1, prev2 + num);
3
用滚动变量压缩状态
每轮更新完当前答案后，让 prev2、prev1 向前滚动。
为什么这样做：转移只依赖前两个状态，不需要整张 DP 数组。
对应代码提示：prev2 = prev1; prev1 = next;
易错点
把偷当前房写成接上一家
这样就违反了不能偷相邻房屋的限制。
正确理解：偷当前房时，必须接的是
prev2 而不是 prev1。边界为空数组时没处理
空输入或只有一间房时，状态初始化容易写崩。
正确理解：先处理长度为 0 和 1 的情况，或统一用滚动变量从 0 开始。
把 DP 数组当必须项
虽然能写对，但空间不是最优，也会让面试解释更绕。
正确理解：优先用两个滚动变量表达前一项和前两项。
复杂度与适用判断
时间复杂度：O(n)
空间复杂度：O(1)
比其他方案更好在哪里：比暴力搜索所有偷法快很多，也能自然扩展到打家劫舍 II、III。
适用判断：线性序列上出现“选当前会影响相邻项”的限制时，优先想到一维 DP。
额外提醒
- 这题的转移不是累加，而是“偷或不偷”的二选一。
动画演示
如果你还没完全看懂，可以展开动画演示。
动态规划动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
动态规划动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
准备就绪 - 输入房屋金额数组，然后点击开始
动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。