leetcode 740. Delete and Earn 抢劫问题的改版 + 动态规划DP

冷不防 2022-06-03 09:48 197阅读 0赞

Given an array nums of integers, you can perform operations on the array.

In each operation, you pick any nums\[i\] and delete it to earn nums\[i\] points. After, you must delete every element equal to nums\[i\] - 1 or nums\[i\] + 1.

You start with 0 points. Return the maximum number of points you can earn by applying such operations.

Example 1:  
Input: nums = \[3, 4, 2\]  
Output: 6  
Explanation:  
Delete 4 to earn 4 points, consequently 3 is also deleted.  
Then, delete 2 to earn 2 points. 6 total points are earned.  
Example 2:  
Input: nums = \[2, 2, 3, 3, 3, 4\]  
Output: 9  
Explanation:  
Delete 3 to earn 3 points, deleting both 2’s and the 4.  
Then, delete 3 again to earn 3 points, and 3 again to earn 3 points.  
9 total points are earned.  
Note:

The length of nums is at most 20000.  
Each element nums\[i\] is an integer in the range \[1, 10000\].

本题题意很简单，这个很像抢劫问题，

这道题给的一个启发就是每当遇到感觉可以遍历来解决的问题的时候，最好先拍一下顺序，然后从头到尾依次计算即可，贪心或者DP动态规划都可以，之前的网易互联网的第一道笔试题：安排路灯问题，就是这个问题的变形，真的需要反思。

建议和[leetcode 337. House Robber III DP动态规划 + DFS深度有限遍历][leetcode 337. House Robber III DP_ _ DFS] 、[leetcode 198. House Robber 入室抢劫 + DP求解][leetcode 198. House Robber _ _ DP] 和 这道题 [leetcode 213. House Robber II 入室抢劫 抢劫问题][leetcode 213. House Robber II _] 一起学习。

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    class Solution 
    {
    public:
        int deleteAndEarn(vector<int>& nums) 
        {
            vector<int> fre(100001, 0);
            for (int a : nums)
                fre[a]++;
    
            vector<int> dp(fre.size(),0);
            dp[0] = fre[0] * 0, dp[1] = fre[1] * 1;
            for (int i = 2; i < fre.size(); i++)
                dp[i] = max(dp[i - 1], fre[i] * i + dp[i - 2]);
    
            return dp[fre.size()-1];
        }
    };

[leetcode 337. House Robber III DP_ _ DFS]: http://blog.csdn.net/jackzhang_123/article/details/78151637
[leetcode 198. House Robber _ _ DP]: http://blog.csdn.net/jackzhang_123/article/details/78037840
[leetcode 213. House Robber II _]: http://blog.csdn.net/jackzhang_123/article/details/78050767