C++刷leetcode（740. 删除与获得点数***）【动态规划】【问题转化】

糖逗

题目描述：

1. 给定一个整数数组 nums ，你可以对它进行一些操作。
   
2. 
   
3. 每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除每个等于 nums[i] - 1 或 nums[i] + 1 的元素。
   
4. 
   
5. 开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
   
6. 
   
7. 示例 1:
   
8. 
   
9. 输入: nums = [3, 4, 2]
   
10. 输出: 6
    
11. 解释:
    
12. 删除 4 来获得 4 个点数，因此 3 也被删除。
    
13. 之后，删除 2 来获得 2 个点数。总共获得 6 个点数。
    
14. 示例 2:
    
15. 
    
16. 输入: nums = [2, 2, 3, 3, 3, 4]
    
17. 输出: 9
    
18. 解释:
    
19. 删除 3 来获得 3 个点数，接着要删除两个 2 和 4 。
    
20. 之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
    
21. 总共获得 9 个点数。
    
22. 注意:
    
23. 
    
24. nums的长度最大为20000。
    
25. 每个整数nums[i]的大小都在[1, 10000]范围内。
    
26. 
    
27. 来源：力扣（LeetCode）
    
28. 链接：https://leetcode-cn.com/problems/delete-and-earn
    
29. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     int deleteAndEarn(vector<int>& nums) {
   
4.         //将问题变型(打家劫舍)
   
5.         int max_num = *max_element(nums.begin(), nums.end());
   
6.         vector<int>store(max_num+1, 0);
   
7.         for(auto num: nums){
   
8.             store[num]++;
   
9.         }
   
10.         //动态规划
    
11.         int len = store.size();
    
12.         vector<int>dp(len, 0);
    
13.         dp[1] = store[1];
    
14.         for(int i = 2; i < len; i++){
    
15.             dp[i] = max(dp[i-1], dp[i-2] + store[i] * i);
    
16.         }
    
17.         return dp[len-1];
    
18.     }
    
19. };

复制代码

糖逗