leecode 740 删除并获得点数

题目描述：

给你一个整数数组 nums ，你可以对它进行一些操作。每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除每个等于 nums[i] - 1 或 nums[i] + 1 的元素。开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/prob

题目测试示例：
示例 1：

输入：nums = [3,4,2]
输出：6
解释：
删除 4 获得 4 个点数，因此 3 也被删除。
之后，删除 2 获得 2 个点数。总共获得 6 个点数。
示例 2：

输入：nums = [2,2,3,3,3,4]
输出：9
解释：
删除 3 获得 3 个点数，接着要删除两个 2 和 4 。
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
总共获得 9 个点数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/delete-and-earn

提示：

1 <= nums.length <= 2 * 104
1 <= nums[i] <= 104

更具体的可以去看原题 对于题目就不多说了

解题思路

简单来说就是动态规划

动态规划 简单来说就是 由n-1--> n 所求量的变化
换算到这个题目 就是说， 我们要推算出 由n-1--> n 最大点数会发生怎样的变化 当然动态规划的起点不要求是0 开始的几个点是可以单独赋值的。

当然有时候在考虑n-1--> n 的时候 也要看一下n-1前面的一些内容 。

那么这个题目怎么动态规划呢？？

前期工作： 统计出每个数出现的次数（或者说： 可贡献的点数）
现在 ，假设我们已经求出0-n-1 的点数（数的范围是0-n-1） x， 当然，我们也知道n-2的点数。同时 ，我们知道 如果我们删除n 那么n-1 就会被间接删除，即点数贡献为0。
如果我们不删，在删除n-1的时候n也会被间接删除，贡献点为0.
所以我们的问题就出在是先删除n-1 还先删除n。 由于我们是求最大点数 ，所以我们只需要求出max(f(n-1),f(n))
好了，到这里 原理及理解个差不多了 。 没看太明白的就在思考思考，

代码

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
    int x[10001];
    memset(x, 0, sizeof(x));// 初始化
    int i;
    for(i=0 ; i<nums.size(); i++)
    {
        x[ nums[i] ]+=nums[i];
        
    }
    int end[10001];
    end[0]=0;
    end[1]=x[1];// 只有1这一种元素
    for(i=2;i<10001;i++)
    {
        end[i]=max(end[i-1],end[i-2]+x[i]);
    }
    return  end[10000];
    }
};

提交结果

执行结果：通过显示详情
执行用时：8 ms,
在所有 C++ 提交中击败了60.06%的用户内存消耗：8.9 MB, 在所有 C++ 提交中击败了65.24%的用户

在提交一次：

执行结果：通过显示详情添加备注
执行用时：4 ms，
在所有 C++ 提交中击败了94.08%的用户内存消耗：8.8 MB, 在所有 C++ 提交中击败了94.82%的用户

当然，解法肯定不唯一 ，欢迎多多指正交流

Leecode740 删除并获得点数

原文：https://www.cnblogs.com/cndccm/p/14731760.html