leetcode 740.删除并活得点数

这道题和打家劫舍得思路很像。

思路：首先我们看到题目的意思，就是说我们如果选择了一个数，那么它相邻的数就会不得选入，也就是删除。这就是上一个题那个相邻的家不能偷的问题呗！

我们从那个地方转换一下，也就是说，我们现在选择的数就是用来偷窃财产的房间号，只不过这个时候房间号相同的个数增加了，不是一个了，所以我们需要计数。由于给出的样例里面数都是相邻的，所以我们需要排个序，因为顺序可能是不一样的，这样不会影响结果。

接下来就按照上一道题的思路写dp的转移方程就行。

注意：首先就是数组的大小开多大的问题，就是按照数据范围开就行。然后，注意尽量不要用nums[i]，你可能会漏了判断n的个数是多少，导致出现数组越界的错误。所以，我们就直接用循环中的i代替就行，因为反正排完序之后顺序就是一样的，数字也是相邻的，所以我们直接用循环变量代替就行了。

上代码：

class Solution {
public:int deleteAndEarn(vector<int>& nums) {sort(nums.begin(),nums.end());int maxs=nums.back();vector<int>dp(10001,0);vector<int>count(10001,0);for(int val:nums)count[val]++;dp[1]=count[1];for(int i=2;i<=maxs;i++){dp[i]=max(dp[i-1],dp[i-2]+i*count[i]);}return dp[maxs];}
};