WHCSRL 技术网

2021-11-01 leetcode 动态规划 740.删除并获取点数 c++

请添加图片描述
题目解释
选定nums数组中一个元素nums[i] = x。
删除nums[i]以及所有等于 x-1或 x+1 的元素。然后,再继续对其他元素进行相同操作。

思路
1: 若选择了 x,所有等于 x 的元素也应一同被选择
解释:在选定x之后,删除值为x和所有值为x+1、x-1的元素。此时,若还有多个值为 x的元素,由于所有等于 x-1或 x+1 的元素已经被删除,我们可以直接删除全部 x 并获得其点数。因此,若选择了 x,所有等于 x 的元素也应一同被选择,以尽可能多地获得点数。

2:用sum[x]将相同元素分别装起来,(cnt 记录每个数重复次数)sum[x]=x*cnt[x],最后在sum上进行操作。
解释:sum[x]为所有x的和,选定x后,则删除x+1和x-1,即不能获取sum[x+1]和sum[x-1]的点数。

综合1,2:问题转化为:对于sum数组,选择其中的元素,如sum[i],删除sum[I]并获取点数,但不能获取sum[I]左右两个元素的点数,即不能获取sum[I+1]和sum[I-1]的点数。现求可得最大点数。和198.打家劫舍思路相同。

动态规划问题关键是求状态转移方程

用dp[i][2]来表示得到的最大点数
dp[i][0]: 第i个元素未进行删除的状态下累积之前的最大点数
dp[i][1]: 第i个元素删除的状态下(删除第i个元素则意味着不删除第i-1个元素)累积之前的最大点数

可得状态转移方程如下
(1)dp[i][0] = max(dp[i-1][0], dp[i-1][1])
(2)dp[i][1] = dp[i-1][0] + nums[i]

AC代码

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        //preparation for sum
        int maxValue = 0;
        // int cnt[l];
        // int sum[l];
        // memset(cnt, 0, sizeof(cnt));
        // memset(sum, 0, sizeof(sum));
        vector<int> sum(10001,0);
        for(int val : nums) {
            sum[val] += val;
            maxValue = max(maxValue, val);
        }
        //operation to sum
        int dp[maxValue+1][2];
        dp[0][0] = 0;
        dp[0][1] = sum[0];
        for(int i = 1; i <= maxValue; i++) {
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
            dp[i][1] = dp[i-1][0] + sum[i];
        }
        return dp[maxValue][0] > dp[maxValue][1] ? dp[maxValue][0] : dp[maxValue][1];
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25

//答案一直不对,以为是中间的问题,换其他方法来做,没想到是返回值出错了!!

推荐阅读