1.题目解析

 题目来源：740.删除并获得点数——力扣

 测试用例

2.算法原理

首先将原数组根据每个数映射为下标，相加后存储在以该数本身为下标的新数组中

1.状态表示

这里与路径问题不同的是每个位置都不止一个状态，因此开辟两个dp表，两个dp表中的dp[i]都表示在第i个位置的最大点数，其中第i个位置可以被预约也可以不被获得

2.状态转移方程

当第i个位置被获得：这就意味着第i-1个位置一定不会被获得点数，此时只需要求出第i-1个位置不被预约时的最大点数加上nums[i]就得出第i个位置的最大点数

当第i个位置不被获得：这代表第i-1个位置可以被获得也可以不被获得，因此需要计算出前一个位置的两种情况后去较大值即可

3.初始化

创建了两个dp表，一个代表指定位置被获得:f，一个代表指定位置不被获得:g，并且状态转移方程中需要用到i-1个位置，因此需要初始化两个dp表的第一个位置

f[0]:第一个位置被获得，直接就是arr[0]，而arr[0]本来就为0，因此不必初始化

g[0]:第一个位置不被获得，则直接为0

4.填表顺序

由于每个位置都需要前一个位置来计算，因此是从左到右填表的顺序

5.返回值

返回最后一个位置是否被获得的两种情况的较大值即可

3.实战代码

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        const int N = 10001;
        int arr[N] = {0};
        vector<int> f(N);
        vector<int> g(N);
        for (auto e : nums) {
            arr[e] += e;
        }

        f[0] = arr[0];
        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]);
    }
};