算法动态规划

打家劫舍：不相邻子序列最大和问题

字数统计: 1.2k字   |   阅读时长: 5分
,

摘要: 不相邻的子序列最大

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 最大子数组和的三种解法 中我们解决了最大组数组和的问题，以该问题为基础问题有很多变种，在文章 目标带绝对值的处理：最大子数组和的绝对值 中做了小结，可以看到，很多变种都是从基础问题的动态规划解法出发解决的。

最大子数组和问题是一维序列上的动态规划的经典问题。如果把子数组改成子序列，要选出和最大的子序列，则选法非常直接，把所有正数都选上即可，与动态规划无关，但如果限制不能选相邻的元素，那么就成为了一维序列上的动态规划的另一个经典问题，该问题也称为打家劫舍问题。本文我们解决这个问题。

198. 打家劫舍

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

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

提示：

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

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

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

算法：动态规划

状态定义 $dp[i]$ 表示考虑到 $i$，在 $nums[0..i]$ 选出的不相邻子序列的最大和。

其中 $i$ 为阶段，仅用阶段即可表示状态。这样定义的话，目标为 $dp[n-1]$，边界值为 $dp[0] = nums[0], dp[1] = \max(nums[0], nums[1])$。

下面考虑状态转移方程：

  • 如果 $nums[i]$ 选入子序列，则 $nums[i-1]$ 不能选，于是 $dp[i] = nums[i] + dp[i - 2]$；
  • 如果 $nums[i]$ 不选入子序列，则 $nums[i - 1]$ 可选可不选，于是 $dp[i] = dp[i - 1]$

综合考虑以上两种情况有：

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n == 0)
            return 0;
        if(n < 2)
            return nums[0];
        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];
    }
};

740. 删除并获得点数

给你一个整数数组 nums ，你可以对它进行一些操作。

每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

提示：

1
2
1 <= nums.length <= 2e4
1 <= nums[i] <= 1e4

示例 1：
输入：nums = [3,4,2]
输出：6
解释：
删除 4 获得 4 个点数，因此 3 也被删除。
之后，删除 2 获得 2 个点数。总共获得 6 个点数。

示例 2：
输入：nums = [2,2,3,3,3,4]
输出：9
解释：
删除 3 获得 3 个点数，接着要删除两个 2 和 4 。
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
总共获得 9 个点数。

算法：规约为打家劫舍

选出了 nums[i]，则 nums[i] - 1 和 nums[i] + 1 就不能选。这与打家劫舍的不相邻子序列问题很像。

由于 nums[i] 的范围是 [1, 10000]，因此可以用一个数组 cnts 记录各个值出现的次数。cnts[x] 表示 nums 中 x 的个数。

然后在 cnt 上做一遍打家劫舍即可，可以直接调用前一题的 rob(cnts)。

代码 (C++)

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        vector<int> weight(10001);
        for(int x: nums)
            weight[x] += x;
        return rob(weight);
    }
};

环形数组上的打家劫舍

在环形数组上也可以求最大子数组和问题，参考文章 环形DP。在 力扣1388-3n块披萨 中我们解决了一个实际问题，可以规约为环形数组上的打家劫舍。

Share