算法 - 打家劫舍

Posted on

1. 题目

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

示例:

1
2
3
4
5
6
7
输入: [1,2,3,1]
输出: 4
解释: 偷 1 号(=1) 和 3 号(=3) 号房屋，1 + 3 = 4。

输入: [2,7,9,3,1]
输出: 12
解释: 偷 1、3、5 号房屋，2 + 9 + 1 = 12。

2. 解题思路

经典「选/不选」线性 DP。

2.1 状态定义

dp[i] = 考虑到第 i 间房时的最高金额。对第 i 间房有两种选择：

  • 不偷 i：dp[i] = dp[i-1]（沿用前一间的最优）。
  • 偷 i：则不能偷 i-1，dp[i] = dp[i-2] + nums[i]。

转移：dp[i] = max(dp[i-1], dp[i-2] + nums[i])。

  • 时间复杂度：O(n)，空间复杂度：O(n) → 优化到 O(1)。

2.2 滚动变量

只用两个变量 prev(dp[i-2]) 与 curr(dp[i-1]) 交替更新，无需数组：每步 ([prev, curr] = [curr, max(curr, prev + num)])。

3. TypeScript 实现

3.1 O(1) 空间（推荐）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function rob(nums: number[]): number {
    let prev = 0; // dp[i-2]
    let curr = 0; // dp[i-1]

    for (const num of nums) {
        const next = Math.max(curr, prev + num);
        prev = curr;
        curr = next;
    }

    return curr;
}

console.log(rob([2, 7, 9, 3, 1])); // 12

3.2 显式 DP 数组（便于理解）

1
2
3
4
5
6
7
8
9
10
function robDP(nums: number[]): number {
    const n = nums.length;
    if (n === 0) return 0;
    const dp = new Array(n).fill(0);
    dp[0] = nums[0];
    for (let i = 1; i < n; i++) {
        dp[i] = Math.max(dp[i - 1], (dp[i - 2] ?? 0) + nums[i]);
    }
    return dp[n - 1];
}

4. 面试延伸

  • 进阶 II：环形街道（House Robber II）——首尾相邻不能同时偷，拆成「不偷首」和「不偷尾」两个线性子问题取 max，max(rob(nums[0..n-2]), rob(nums[1..n-1]))。
  • 进阶 III：树形 DP（House Robber III）——在二叉树上做「偷当前根 vs 偷左右子」的决策，后序 DFS 返回 [不偷, 偷] 一对值，是树形 DP 模板。
  • 本题是「最大子序列和 / 股票买卖」等同族「每步二选一」DP 的原型，掌握状态定义 + 滚动优化即可通吃。

难度：中等 | LeetCode 198 | 线性 DP