0198.打家劫舍
难度：🟡 中等
标签：数组、动态规划
链接：198. 打家劫舍
题目描述
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：nums = [1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：nums = [2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
解题思路
核心思想
本题是动态规划的经典应用场景。问题的核心在于，对于每一间房屋，我们都有两种选择：偷 或者 不偷。我们的决策会受到“不能偷相邻房屋”的约束。
如果我们决定 偷 第
i间房屋，那么我们就不能偷第i-1间，此时能获得的最大金额是 “偷到第i-2间的最大金额” 加上 “第i间的金额”。如果我们决定 不偷 第
i间房屋，那么此时能获得的最大金额就等于 “偷到第i-1间的最大金额”。
我们的目标就是在这些决策中，找出能使总金额最大化的那条路。
思路选择
动态规划 (Dynamic Programming) 是解决此问题的标准最优思路。
我们可以定义
dp[i]为考虑前i间房屋（从第 0 间到第i-1间）所能偷窃到的最高金额。状态转移方程 的推导如下：对于第
i间房（nums[i-1]），dp[i]的值取决于我们是否偷这间房：偷:
(dp[i-2] || 0) + nums[i-1]不偷:
dp[i-1]
我们取这两者的较大值，即
dp[i] = Math.max(dp[i-1], (dp[i-2] || 0) + nums[i-1])。观察发现，计算
dp[i]只需要dp[i-1]和dp[i-2]。因此，我们无需创建完整的dp数组，只需用两个变量来滚动记录前两个状态即可，实现空间优化。
关键步骤
处理边界情况：如果数组为空，返回 0。如果只有一个元素，返回该元素。
初始化：初始化两个变量，
prev代表偷到i-2间房的最大金额，curr代表偷到i-1间房的最大金额。循环迭代：从第 3 间房（索引 2）开始遍历。 a. 在循环中，计算偷到当前房间
i的最大金额，即Math.max(curr, prev + nums[i])。 b. “滚动”更新prev和curr的值，为下一次计算做准备。返回结果：循环结束后，
curr中存储的就是最终的最高金额。
代码实现
/**
* @param {number[]} nums
* @return {number}
*/
var rob = function(nums) {
if (nums.length === 0) return 0;
// prev 代表 dp[i-2], curr 代表 dp[i-1]
let prev = 0;
let curr = 0;
for (const num of nums) {
// 暂存上一个状态
const temp = curr;
// 计算当前状态：max(不偷当前房, 偷当前房)
curr = Math.max(curr, prev + num);
// 更新上一个状态
prev = temp;
}
return curr;
};
复杂度分析
时间复杂度：O(n) 其中 n 是数组
nums的长度。我们只需要对数组进行一次完整的遍历。空间复杂度：O(1) 推荐解法只使用了常数个额外变量，空间消耗是恒定的。
相关题目
总结
本题是动态规划中的经典线性DP问题。其核心在于正确定义状态 dp[i] 并推导出状态转移方程。通过滚动数组的思想进行空间优化，是从 O(n) 到 O(1) 空间复杂度的关键一步，是面试中常见的考察点。