06、打家劫舍

今天继续来说一道经典的题目，打家劫舍

https://leetcode.cn/problems/house-robber/

题目描述

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

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

示例 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 。

约束条件:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

此时我们想了，这有啥难的？我们直接搁位置偷呗，确实如此，所以这个题目就改成了，从哪个房间开始偷，以及偷的过程中，需要搁几个空的问题。

比如 4,1,1,1,1,9 这种情况，我们思考一下，怎么偷才能收益最大化呢？

问题理解

关键约束

限制：不能偷相邻的房屋

房屋：  [2, 7, 9, 3, 1]
索引：   0  1  2  3  4

如果偷 0，就不能偷 1
如果偷 1，就不能偷 0 和 2
如果偷 2，就不能偷 1 和 3
...

问题：在这个约束下，能偷到的最大金额是多少？

决策分析

对于第 i 个房屋，有两种选择：

选择1：偷第 i 个房屋
  - 获得金额：nums[i]
  - 但不能偷第 i-1 个房屋
  - 所以加上第 i-2 个房屋之前的最大金额
  - 总金额：nums[i] + dp[i-2]

选择2：不偷第 i 个房屋
  - 金额：0
  - 可以偷第 i-1 个房屋
  - 总金额：dp[i-1]

选择金额较大的方案：
dp[i] = max(nums[i] + dp[i-2], dp[i-1])

示例分析

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

所有可能方案（部分）：

方案1：偷 0, 2, 4 → 2 + 9 + 1 = 12 ✓ 最大
方案2：偷 1, 3    → 7 + 3     = 10
方案3：偷 0, 3    → 2 + 3     = 5
方案4：偷 1, 4    → 7 + 1     = 8
方案5：偷 0, 2    → 2 + 9     = 11

最大金额：12

动态规划解法⭐

DP 五部曲

1. 确定 dp 数组及下标含义
   dp[i] 表示偷窃前 i 个房屋能获得的最大金额

2. 确定递推公式
   dp[i] = max(dp[i-1], nums[i] + dp[i-2])

   不偷第 i 个 vs 偷第 i 个

3. dp 数组如何初始化
   dp[0] = nums[0]  （只有一个房屋，直接偷）
   dp[1] = max(nums[0], nums[1])  （两个房屋，偷金额大的）

4. 确定遍历顺序
   从前往后，i 从 2 到 n-1

5. 举例推导 dp 数组
   见下方详细示例

详细图解示例

以示例2为例：nums = [2, 7, 9, 3, 1]

步骤1: 初始化
dp[0] = nums[0] = 2
dp[1] = max(nums[0], nums[1]) = max(2, 7) = 7

dp = [2, 7, ?, ?, ?]


步骤2: 计算 dp[2]
不偷房屋2：dp[1] = 7
偷房屋2：nums[2] + dp[0] = 9 + 2 = 11
dp[2] = max(7, 11) = 11

dp = [2, 7, 11, ?, ?]

当前最优方案：偷 0, 2 → 2 + 9 = 11


步骤3: 计算 dp[3]
不偷房屋3：dp[2] = 11
偷房屋3：nums[3] + dp[1] = 3 + 7 = 10
dp[3] = max(11, 10) = 11

dp = [2, 7, 11, 11, ?]

当前最优方案：保持偷 0, 2 → 11


步骤4: 计算 dp[4]
不偷房屋4：dp[3] = 11
偷房屋4：nums[4] + dp[2] = 1 + 11 = 12
dp[4] = max(11, 12) = 12

dp = [2, 7, 11, 11, 12]

最优方案：偷 0, 2, 4 → 2 + 9 + 1 = 12


最终答案：dp[4] = 12 ✓

代码实现

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return 0;
        }

        if (n == 1) {
            return nums[0];
        }
        // 创建 dp 数组
        vector<int> dp(n);

        // 初始化
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);

        // 状态转移
        for (int i = 2; i < n; i++) {
            dp[i] = max(dp[i-1], nums[i] + dp[i-2]);
        }

        return dp[n-1];
    }
};

时间复杂度: O(n)，遍历一次数组

空间复杂度: O(n)，dp 数组

空间优化⭐⭐

优化思路

观察到 dp[i] 只依赖 dp[i-1] 和 dp[i-2]，只需要两个变量。

代码实现

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
           return 0;
        }
        if (n == 1) {
            return nums[0];
        }

        // 只需要两个变量
        int prev2 = nums[0];                    // dp[i-2]
        int prev1 = max(nums[0], nums[1]);      // dp[i-1]

        // 从第 3 个房屋开始
        for (int i = 2; i < n; i++) {
            int curr = max(prev1, nums[i] + prev2);

            // 滚动更新
            prev2 = prev1;
            prev1 = curr;
        }

        return prev1;
    }
};

时间复杂度: O(n)

空间复杂度: O(1)