原题链接

这道题也是有限制的选择问题，可以使用动态规划解决。

f(i,0)f(i,0) 表示只考虑 1 ~ i 这些数，不选 i 的选法中获得点数的最大值。由于不选 i，那么可以将问题划分成考虑前 i-1 个数，选 i-1、不选 i-1，所以 f(i,0)=max{f(i−1,1),f(i−1,0)}f(i,0)=max\{f(i-1,1),f(i-1,0)\}

f(i,1)f(i,1) 表示只考虑 1 ~ i 这些数，选 i 的选法中获得点数的最大值。由于选 i，那么不能选 i-1，所以 f(i,1)=f(i−1,0)+i∗cif(i,1)=f(i-1,0)+i*c_i。cic_i 表示数组中有几个 i 这个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int N = 10010;
int cnt[N], f[N][2];

class Solution {
 public:
  int deleteAndEarn(vector<int>& nums) {
    memset(cnt, 0, sizeof cnt);
    memset(f, 0, sizeof f);
    for (auto x : nums) cnt[x]++;
    int res = 0;
    for (int i = 1; i < N; i++) {
      f[i][0] = max(f[i - 1][0], f[i - 1][1]);
      f[i][1] = f[i - 1][0] + i * cnt[i];
      res = max(res, max(f[i][0], f[i][1]));
    }
    return res;
  }
};