思路
有限制的选择问题 选择i就要删除所有的i-1和i 1 讨论当前状态i
- (1)如果选择了i，则i 1不能选
- (2)如果不选择i，则i 1可以选也可以不选
状态表示：
- f[i][0]表示只考虑前i个数，不选择i所有选法中所能得到的最大值；
- f[i][1]表示只考虑前i个数，选择i所有选法中所能得到的最大值； 状态计算：
- 如果当前i不选，则考虑前
i-1个数所能获得的最大值。这时有需要考虑选择不选i-1，如果选择i-1则前i-1个数所能获得的最大值就是f[i-1][1];如果不选择i-1则前i-1个数所能获得的最大值就是f[i-1][0]；即可得到下边的状态转移方程，f[i][0] = max(f[i-1][0], f[i-1][1]); - 如果当前i必选，则i-1必不选；考虑前i-1个数所能获得的最大值，即是
f[i-1][0]；同时还要加上i乘以当前i的个数；即可得到下边的状态转移方程，f[i][1] = f[i-1][0] i * cnt[i];
代码
代码语言：javascript复制const int N = 1e4 10;
int cnt[N];
int f[N][2];
class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
memset(cnt, 0, sizeof(cnt));
memset(f, 0, sizeof(f));
int n = nums.size();
for (auto x: nums) {
cnt[x] ;
}
int ans = INT_MIN;
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];
ans = max(ans, max(f[i][1], f[i][0]));
}
return ans;
}
};
