## 题目描述：

LeetCode 740. Delete and Earn

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[x]表示删除不大于x的所有数字的最大得分。

cnt[x]存储数字x的个数。```

`dp[x] = max(dp[x - 1], dp[x - 2] + cnt[x] * x)`

## Python代码：

``````class Solution(object):
def deleteAndEarn(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
cnt = collections.Counter(nums)
maxn = max(nums + )
dp =  * (maxn + 10)
for x in range(1, maxn + 1):
dp[x] = max(dp[x - 1], dp[x - 2] + cnt[x] * x)
return dp[maxn]
``````

Pingbacks已关闭。