[动态规划] (十三) 简单多状态: LeetCode 740.删除并获得点数

740. 删除并获得点数

题目解析

(1) 给定一个整数数组。

(2) 选择一个nums[i]，获得所有nums[i]的和，删除nums[i] - 1和nums[i] + 1。

(3) 一开始你有0个点数，返回你能获得的最大点数

解题思路

通过题目解析，我们发现这和我们之前做的打家劫舍和按摩师有一些共同之处。

假设一个数组是[1，2，3，4]，如果我们选择了3，那就不能选择2和4。

那么，我们把这个重复出现的数字，归到同一下标位置，是不是就可以将它转换为打家劫舍问题呢？(预处理)我们来试试：

我们可以取2-0-5-7或者2-8-12-24等等情况，这就和我们之前做的打家劫舍几乎一模一样了。

状态表示

dp[i]：按照往常的经验，以i为终点，可以获得的最大点数。

i位置，我们有可以选择，获取或者不获取

f[i]:表示获取i位置的点数

g[i]:表示不获取i位置的点数

状态转移方程

f[i]：当我们需要获取i位置的点数时，那么i-1位置必然不获取。

所以我们只用i-1之前的点数加上对应当前位置的点数即可。

f[i] = g[i-1] + nums[i]

g[i]：当我们不获取i位置时，那么i-1位置又可以获取，也可以不获取，我们只需要取最大值即可。对应状态表示，获取i-1位置就是f[i-1]，不获取i-1就是g[i-1]

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

初始化和填表顺序

• 初始化

因为我们在刚刚举例子时，发现新的数组会多出一个0位置的元素，所以我们可以多初始化一个虚拟节点，这可以让我们下标对应更加简单。

我们把虚拟出的节点初始化为0即可，容器在扩容时又会自动帮我们初始化为0，所以我们不需要手动初始化。

• 填表顺序

从左到右。

返回值

多了一个虚拟节点，返回n位置的较大值即可。

看到这里，可以尝试手动实现代码，再来看下面的内容。

---

代码实现

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        //预处理
        const int cnt = 10001;
        int arr[cnt] = {0};
        for(auto e : nums) arr[e] += e;
        //创建dp表
        vector<int> f(cnt);
        vector<int> g(cnt);
        //初始化
        // f[0] = arr[0], g[0] = 0;
        //填表
        for(int i = 1; i < cnt; i++)
        {
            f[i] = g[i-1] + arr[i];
            g[i] = max(f[i-1], g[i-1]);
        }
        //返回值
        return max(f[cnt-1], g[cnt-1]);
    }
};

总结

细节1：多多联系我们之前做过的题，看看新的题与我们之前做过的题有没有什么通性。

细节2：预处理数组的空间我们比题目给的多扩了1个，所以返回值n位置即为，我们扩的容量-1。