动态规划 —— 打家劫舍问题及其变式总结

前言#

除了爬楼梯类问题外，入门DP的另一大类即是打家劫舍问题。

题单⬆️（0x3F总结版，特别鸣谢）

例题：Leetcode 198.打家劫舍#

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

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

示例 1：

1
输入：[1,2,3,1]
2
输出：4
3
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
4
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

1
输入：[2,7,9,3,1]
2
输出：12
3
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
4
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

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

题目思路#

首先考虑最简单的情况。如果只有一间房屋，则偷窃该房屋，可以偷窃到最高总金额。如果只有两间房屋，则由于两间房屋相邻，不能同时偷窃，只能偷窃其中的一间房屋，因此选择其中金额较高的房屋进行偷窃，可以偷窃到最高总金额。

如果房屋数量大于两间，应该如何计算能够偷窃到的最高总金额呢？对于第 k (k>2) 间房屋，有两个选项：

偷窃第 k 间房屋，那么就不能偷窃第 k−1 间房屋，偷窃总金额为前 k−2 间房屋的最高总金额与第 k 间房屋的金额之和。

不偷窃第 k 间房屋，偷窃总金额为前 k−1 间房屋的最高总金额。

在两个选项中选择偷窃总金额较大的选项，该选项对应的偷窃总金额即为前 k 间房屋能偷窃到的最高总金额。

用 dp[i] 表示前 i 间房屋能偷窃到的最高总金额，那么就有如下的状态转移方程：

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

边界条件为：

dp[0]=nums[0] dp[1]=max(nums[0],nums[1]) 只有一间房屋，则偷窃该房屋只有两间房屋，选择其中金额较高的房屋进行偷窃最终的答案即为 dp[n−1]，其中 n 是数组的长度。

代码#

1
class Solution {
2
public:
3
    int rob(vector<int>& nums) {
4
        int n = nums.size();
5

6
        if(nums.empty()) {
7
            return 0;
8
        }
9
        if (n == 1) {
10
            return nums[0];
11
        }
12

13
        vector<int>dp (n, 0);
14
        dp[0] = nums[0];
15
        dp[1] = max(nums[0], nums[1]);
16
        for (int i = 2;i < n; i++) {
17
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
18
        }
19

20
        return dp[n - 1];
21
    }
22
};

其他变式#

好，你现在已经学会最基本的打家劫舍了，那我们试着加一点难度。

740. 删除并获得点数#

思路&&代码#

这道题与打家劫舍极为相似，只需遍历nums，用一个数组points[i] 表示每个i * 次数

1
class Solution {
2
public:
3
    int deleteAndEarn(vector<int>& nums) {
4
        if (nums.empty()) {
5
            return 0;
6
        }
7
        int maxVal = *max_element(nums.begin(), nums.end());
8
        vector<int> points(maxVal + 1, 0);
9
        vector<int> dp(maxVal + 1, 0);
10
        for (int num : nums) {
11
            points[num] += num;
12
        }
13
        dp[1] = points[1];
14
        for (int i = 2; i <= maxVal; i++) {
15
            dp[i] = max(dp[i - 1], dp[i - 2] + points[i]);
16
        }
17
        return dp[maxVal];
18
    }
19
};
20
### 2320. 统计放置房子的方式数
21

22

23
#### 思路&&代码
24

25

26
这个题可以把每一侧道路都看作一个“不能放邻近房子” 问题，因此，单侧就变成了一个经典的斐波那契型递归问题。
27

28

29
而两侧结果是独立的 互不影响，因此最后结果是单侧的平方
30

31

32
```cpp
33
class Solution {
34
public:
35
    int countHousePlacements(int n) {
36
        const int MOD = 1e9 + 7;
37
        vector<long long> dp(n + 1, 0);
38
        dp[0] = 1;
39
        dp[1] = 2;
40
        for (int i = 2; i <= n; i++) {
41
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
42
        }
43
        long long res = (dp[n] * dp[n]) % MOD;
44
        return res;
45
    }
46
};
47
#### ***Tip
48

49

50
补充非常重要的一点 ： 在代码中，我们取模了两次，因此有同学可能会疑惑，取模两次会不会造成错误结果。
51

52

53
其实，这是一个非常常见的问题，在for循环中的，dp[i] 取模式为了防止中间爆 long long 因此必须取余一次。
54

55

56
** 所以，我们通常的做法是：**
57

58

59
• 所有加法中都及时 % MOD，防止中间结果超限；
60

61

62
• 最后再对乘法结果 % MOD，是对的；
63

64

65
• **即使前面的 dp[n] 已经 % MOD，我们也要对最终乘积 res 再 % MOD。**
66

67

68
为什么？
69

70

71
举个例子说明：
72

73

74
```cpp
75
MOD = 1000000007;
76
dp[n] = 1000000006; // 即使已经 % MOD
77
res = (dp[n] * dp[n]) % MOD;
78
// 即 (1000000006 * 1000000006) % MOD = 1

如果不在res中 % MOD ，可能res会溢出。

综上所述，对dp取余，又对res取余不是重复，是必须的！

213. 打家劫舍 II#

思路&&代码#

本题与打家劫舍 I 主要区别在于房子形成环形，因此，我们可以把环拆成两种情况处理，

不偷第一个房子考虑区间【1，n - 1】
不偷最后一个房子考虑区间【0，n - 2】

因此，我们可以讲打家劫舍 I 的函数封装为一个函数，并分别带入两种情况，求出最大值。

代码如下：

1
class Solution {
2
public:
3
    int robb(vector<int>& nums, int start, int end) {
4
        int len = end - start + 1;
5
        if (len == 1) {
6
            return nums[start];
7
        }
8
        vector<int> dp(len, 0);
9
        dp[0] = nums[start];
10
        dp[1] = max(nums[start], nums[start + 1]);
11
        for (int i = 2; i < len; i++) {
12
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[start + i]);
13
        }
14
        return dp[len - 1];
15
    }
16
    int rob(vector<int>& nums) {
17
        int n = nums.size();
18
        if (n == 0) return 0;
19
        if (n == 1) return nums[0];
20
        //不偷第一个
21
        int case1 = robb(nums, 1, n - 1);
22
        //不偷最后一个
23
        int case2 = robb(nums, 0, n - 2);
24
        return max(case1, case2);
25
    }
26
};

代码中有一下需注意⚠️：

在robb 函数中，需加入 if 判断以避免求 dp[1] 时报错
robb函数中nums是从 start 开始的，不要傻乎乎写 nums[0] nums[i] 哦

3186. 施咒的最大总伤害#

思路&&代码#

1
/// dp[i] = max(dp[x]..., dp[y] + power[i] * count[power[i]])  :
2
        ///     power[i] > power[x] >= power[i] - 2}
3
        ///     y（y<i)是第一个满足‘power[y] < power[i] - 2’的索引
4
class Solution {
5
public:
6
    long long maximumTotalDamage(vector<int>& power) {
7
        /// 记录每个‘伤害’的个数
8
        unordered_map<long long, long long> countMap;
9
        for (int x : power) countMap[x]++;
10

11
        /// 排序
12
        sort(power.begin(), power.end());
13

14
        /// 去重
15
        auto new_end = unique(power.begin(), power.end());
16
        power.erase(new_end, power.end());
17

18
        //DP
19
        int size = power.size();
20
        vector<long long> dp(size);
21
        dp[0] = countMap[power[0]] * power[0];
22

23
        long long result = dp[0];
24
        for (int i = 0; i < size; i++) {
25
            long long curVal = power[i] * countMap[power[i]];
26
            dp[i] = curVal;
27
            for (int j = 1; j <= 3; j++) {
28
                if (i - j < 0) continue;
29

30
                if (power[i] - 2 > power[i - j]) {
31
                    dp[i] = max(dp[i], dp[i - j] + curVal);
32
                    break;
33
                } else {
34
                    dp[i] = max(dp[i], dp[i - j]);
35
                }
36
            }
37
            result = max(result, dp[i]);
38
        }
39
        return result;
40
    }
41
};

原文发布于 CSDN：动态规划 —— 打家劫舍问题及其变式总结

前言#

例题 ：Leetcode 198.打家劫舍#

题目思路#

代码#

其他变式#

740. 删除并获得点数#

思路&&代码#

213. 打家劫舍 II#

思路&&代码#

3186. 施咒的最大总伤害#

思路&&代码#

例题：Leetcode 198.打家劫舍#