740 删除并获得点数（递推）

阳光穿透心脏的1/2处 2022-09-10 07:11 17阅读 0赞

**1. 问题描述：**

给你一个整数数组 nums ，你可以对它进行一些操作。每次操作中，选择任意一个 nums\[i\] ，删除它并获得 nums\[i\] 的点数。之后，你必须删除所有等于 nums\[i\] - 1 和 nums\[i\] + 1 的元素。开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

**示例 1：**

输入：nums = \[3,4,2\]  
输出：6

**解释：**

删除 4 获得 4 个点数，因此 3 也被删除。  
之后，删除 2 获得 2 个点数。总共获得 6 个点数。

**示例 2：**

输入：nums = \[2,2,3,3,3,4\]  
输出：9

**解释：**

删除 3 获得 3 个点数，接着要删除两个 2 和 4 。  
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。  
总共获得 9 个点数。

**提示：**

1 <= nums.length <= 2 \* 10 ^ 4  
1 <= nums\[i\] <= 10 ^ 4  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/delete-and-earn

**2. 思路分析：**

这道题目类似于力扣的198题，分析题目可以知道我们需要求解出一个最优的方案使得能够获得最大的点数，所以我们需要尝试求解出所有可能的方案从而求解出最优的那个方案，对于这种尝试所有可能性并且求解最优方案的题目我们一般可以使用**动态规划**或者**递归**来解决（最优化问题），对于数据规模比较大的题目一般使用动态规划解决，对于这道题目来说数据规模较大所以使用动态规划思想来解决（这里可以使用递推来解决）。可以发现对于当前的值为nums\[i\]的元素只与相邻的两个元素有关，分别是nums\[i\] - 1与nums\[i\] + 1，而对于nums\[i\]这个元素存在两种策略，分别是**选择**删除nums\[i\]与**不选择**删除nums\[i\]，所以我们可以定义一个二维数组或者二维列表，其中dp\[i\]\[j\]表示前i个数中删除第i个数字或者不删除第i个数的能够获得的最大点数，j = 0或者j = 1，j = 0表示不删除第i个元素，j = 1表示删除第i个元素，在选择删或者不删第i个元素的时候只会影响相邻两个数字，所以状态转移方程为dp\[i\]\[0\] = max(dp\[i - 1\]\[0\], dp\[i - 1\]\[1\])，dp\[i\]\[1\] = dp\[i - 1\]\[0\] + count\[i\] \* i，其中count\[i\]表示数字i出现的次数，我们可以在一开始的时候遍历nums，对nums中的数字进行计数即可。

**3. 代码如下：**

from typing import List
    
    
    class Solution:
        def deleteAndEarn(self, nums: List[int]) -> int:
            n = 10010
            count = [0] * n
            dp = [[0] * 2 for i in range(n)]
            # 计算每一个数字出现的次数
            for x in nums:
                count[x] += 1
            res = 0
            for i in range(1, n):
                # 前i个数中不选择第i个数删除
                dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])
                # 前i个数中选择第i个数删除
                dp[i][1] = dp[i - 1][0] + count[i] * i
                res = max(dp[i][0], dp[i][1])
            return res