[!info] related notes 算法面试题型 MOC 动态规划 线性 DP

打家劫舍

题目链接：https://leetcode.cn/problems/house-robber/

题意

给你一个数组 nums，nums[i] 表示第 i 个房子的金额。不能偷相邻两个房子，求最多能偷多少钱。

为什么是 DP

• 每个位置都面临“偷 / 不偷”的决策
• 当前答案依赖前面更小规模问题
• 暴力递归会重复计算 dfs(i)

状态

定义 dp[i] 表示考虑前 i + 1 个房子时的最大收益。

转移

• 不偷第 i 个：dp[i - 1]
• 偷第 i 个：dp[i - 2] + nums[i]

所以：

dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

边界

• dp[0] = nums[0]
• dp[1] = max(nums[0], nums[1])

样例

nums = [2, 7, 9, 3, 1]

• dp[0] = 2
• dp[1] = 7
• dp[2] = 11
• dp[3] = 11
• dp[4] = 12

答案：12

JavaScript

var rob = function(nums) {
    const n = nums.length;
    if (n === 1) return nums[0];

    const dp = new Array(n).fill(0);
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);

    for (let i = 2; i < n; i++) {
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
    }

    return dp[n - 1];
};

空间优化

只依赖前两个状态，可以压成两个变量。

易错点

• n = 1 要单独处理
• 状态含义要写清楚，是“前 i 个房子”而不是“以 i 结尾”