【学会动态规划】删除并获得点数（13）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【学会动态规划】删除并获得点数（13）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

动态规划怎么学？

1. 题目解析

2. 算法原理

1. 状态表示

2. 状态转移方程

3. 初始化

4. 填表顺序

5. 返回值

3. 代码编写

写在最后：

动态规划怎么学？

学习一个算法没有捷径，更何况是学习动态规划，

跟我一起刷动态规划算法题，一起学会动态规划！

1. 题目解析

题目链接：740. 删除并获得点数 - 力扣（Leetcode）

【学会动态规划】删除并获得点数（13）,学会动态规划,动态规划,算法,c++,学习

这道题比较抽象，我就拿他给的样例举例子吧，

【学会动态规划】删除并获得点数（13）,学会动态规划,动态规划,算法,c++,学习

如果选择 3，就需要把 4 和 2 都删除，那么点数就是 3

如果选择 2，就需要把 1 和 3 都删除，那么继续选择 4 ，需要把 3 和 5 删除，

最后点数加在一起就是 2 + 4 = 6，最大点数是 6 所以返回 6。

同理，第二个示例：

【学会动态规划】删除并获得点数（13）,学会动态规划,动态规划,算法,c++,学习

还是两种情况，选 2，4，或者选 3。

注意是选择一个数之后，这数 + 1 和 - 1 就会被删除。

实际上，这道题如果直接做的话并不好做，

我们可以对他进行一些预处理的操作，来转化成我们熟悉的问题：

这里我还是用题目给的示例演示：

【学会动态规划】删除并获得点数（13）,学会动态规划,动态规划,算法,c++,学习

我们通过下标对应点数的形式，转化出一个新数组：

【学会动态规划】删除并获得点数（13）,学会动态规划,动态规划,算法,c++,学习

比如说，原数组从 2 开始，那点数数组下标为 2 的位置就是点数 2 + 2 = 4，

然后下标为 3 的位置点数就是 3 + 3 = 6，下标为 4 的位置点数就是 4 。

这样做，就能把这个问题转化成打家劫舍的问题了：相邻的下标不能同时选择。

2. 算法原理

1. 状态表示

然后这个问题就有两种情况，：

f [ i ] 表示选到 i 位置的时候，nums[ i ] 选，此时能得到的最大点数

g [ i ] 表示选到 i 位置的时候，nums[ i ] 不选，此时能得到的最大点数

2. 状态转移方程

所以状态转移方程也有两个，

选 i 位置，就是nums[ i ] + 不选 i - 1 位置的情况：f [ i ] = g[ i - 1 ] + nums[ i ]

g[ i ] = max( f [ i - 1 ]，g[ i - 1 ] )

3. 初始化

f [ 0 ] = nums[ 0 ]，g[ 0 ] = 0。

4. 填表顺序

从左往右

5. 返回值

max( f [ n - 1 ]，g[ n - 1 ] )

3. 代码编写

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<int> dp(nums[nums.size() - 1] + 1);
        for(auto e : nums) dp[e] += e;
        int n = dp.size();
        vector<int> f(n);
        auto g = f;
        f[0] = dp[0];
        for(int i = 1; i < n; i++) {
            f[i] = g[i - 1] + dp[i];
            g[i] = max(f[i - 1], g[i - 1]);
        }
        return max(f[n - 1], g[n - 1]);
    }
};