Leetcode刷题详解——删除并获得点数

1. 题目链接：740. 删除并获得点数

2. 题目描述：

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

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

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

示例 1：

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

示例 2：

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

提示：

• 1 <= nums.length <= 2 * 104
• 1 <= nums[i] <= 104

3. 解法（动态规划）：

3.1 算法思路：

1. 定义一个常量N，表示数组的最大值加1。这里假设输入数组nums中的元素都是非负整数，并且小于等于N-1。
2. 创建一个长度为N的整数数组arr，并初始化为0。这个数组用于存储每个元素出现的次数。
3. 遍历输入数组nums，将每个元素的值累加到对应的arr数组位置上。这样可以统计每个元素出现的次数。
4. 创建一个长度为N的整数向量f，用于存储动态规划的状态。这个向量f[i]表示在考虑前i个元素时可以获得的最大收益。
5. 创建一个引用g，指向向量f，以便在后续计算中使用。
6. 使用循环迭代计算状态转移方程。从i=1开始，依次计算f[i]和g[i]的值。
   • f[i] = g[i - 1] + arr[i]：表示在考虑前i个元素时，可以选择当前元素或者不选择当前元素。
   • g[i] = max(f[i - 1], g[i - 1])：表示在考虑前i个元素时，可以选择当前元素或者不选择当前元素。
7. 返回最终结果，即最大收益。可以通过比较f[N - 1]和g[N - 1]的值来得到最大收益。

3.2 C++算法代码：

class Solution {
public:
    int deleteAndEarn(vector& nums) {
        const int N = 10001; // 定义一个常量N，表示数组的最大值加1
        int arr[N] = {0}; // 创建一个长度为N的整数数组arr，并初始化为0
        for (auto x : nums) arr[x] += x; // 遍历输入数组nums，将每个元素的值累加到对应的arr数组位置上
        vector f(N); // 创建一个长度为N的整数向量f，用于存储动态规划的状态
        auto g = f; // 创建一个引用g，指向向量f，以便在后续计算中使用
        for (int i = 1; i < N; i++) {
            f[i] = g[i - 1] + arr[i]; // 更新状态转移方程，计算当前位置的最大收益
            g[i] = max(f[i - 1], g[i - 1]); // 更新状态转移方程，计算当前位置的最大收益（不选择当前元素）
        }
        return max(f[N - 1], g[N - 1]); // 返回最终结果，即最大收益
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15