###### tags: `Leetcode` `medium` `dynamic programming` `array` `python` `c++`

# 740. Delete and Earn

## [題目連結:] https://leetcode.com/problems/delete-and-earn/description/

## 題目:
You are given an integer array ```nums```. You want to maximize the number of points you get by performing the following operation any number of times:

* Pick any ```nums[i]``` and delete it to earn ```nums[i]``` points. Afterwards, you must delete **every** element equal to ```nums[i] - 1``` and **every** element equal to ```nums[i] + 1```.

Return the **maximum number of points** you can earn by applying the above operation some number of times.

**Example 1:**

Input: nums = [3,4,2]
Output: 6
Explanation: You can perform the following operations:
- Delete 4 to earn 4 points. Consequently, 3 is also deleted. nums = [2].
- Delete 2 to earn 2 points. nums = [].
You earn a total of 6 points.

**Example 2:**

Input: nums = [2,2,3,3,3,4]
Output: 9
Explanation: You can perform the following operations:
- Delete a 3 to earn 3 points. All 2's and 4's are also deleted. nums = [3,3].
- Delete a 3 again to earn 3 points. nums = [3].
- Delete a 3 once more to earn 3 points. nums = [].
You earn a total of 9 points.

## 解題想法:
* 此題為給一數組，每次選擇任一nums[i]，刪除並獲得nums[i]的點數，且必須刪除每個等於nums[i]+1或nums[i]-1的數
* 求能獲得的最大總數
* 起始動作:
* 題目規定: 1 <= nums[i] <= 104
* 數字對多到10000，先記錄所有數出現的總和

    sum=[0]*10001
    for i in nums: #先填入各數字加總
        sum[i]+=i

* **Sol1**使用DP:
* 定義兩組dp
* token=[0] * 10001 :**拿該數**
* init: token[0]=sum[0]
* skip=[0] * 10001 :**不拿該數**
* 轉移方程式:
* 取: max(上個數有取vs上個數沒取+取當前數字)

        token[i]=max(token[i-1],skip[i-1]+sum[i])

* 不取: max(上個數不取vs上個數有取)

        skip[i]=max(skip[i-1],token[i-1])

* return max(token[-1], skip[-1])

* **Sol2**:
* 視為house robber不能搶鄰居 [198. House Robber](/YIzmiuAqRfm6voICu36IXg)

## Python:

class Solution(object):
    def deleteAndEarn(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        #法1
        sum=[0]*10001
        for i in nums:
            sum[i]+=i
        token=[0]*10001 #拿該數
        skip=[0]*10001 #不拿該數
        token[0]=sum[0]
        for i in range(1,10001):
            #取: max(上個數有取vs上個數沒取+當前數字)
            token[i]=max(token[i-1],skip[i-1]+sum[i])
            #不取: max(上個數不取vs上個數有取)
            skip[i]=max(skip[i-1],token[i-1])
        return max(token[-1],skip[-1])

        #法2
        #數字最多到10000
        sum=[0]*(10001)
        #先填入各數字加總
        for i in nums:
            sum[i]+=i
        #因為i從 2 3 4.... 可以看成house robber不能搶鄰居
        for i in range(2,10001):
            sum[i]=max(sum[i-1],sum[i-2]+sum[i])
        return sum[-1]

ressult=Solution()
ans=ressult.deleteAndEarn(nums = [2,2,3,3,3,4])
print(ans)

## C++:

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        vector<int> sum(10001, 0), token(10001, 0), skip(10001, 0);
        for (int val: nums) sum[val]+=val;
        token[0]=sum[0];
        for (int i=1; i<10001; i++){
            token[i]=max(token[i-1], skip[i-1]+sum[i]);
            skip[i]=max(skip[i-1], token[i-1]);
        }
        return max(token[10000], skip[10000]);
    }
};