【LeetCode】动态规划—删除并获得点数（附完整Python/C++代码）

动态规划—#740. 删除并获得点数

• 前言
• 题目描述
• 基本思路
  • 1. 问题定义:
  • 2. 理解问题和递推关系:
  • 3. 解决方法:
  • 4. 进一步优化:
  • 5. 小总结:
• 代码实现
• • Python3代码实现
  • Python 代码解释
  • C++代码实现
  • C++ 代码解释
• 总结:

前言

给你一个整数数组

，你可以对它进行一些操作。

每次操作中，选择任意一个 n u m s [ i ] nums[i] nums[i] ，删除它并获得 n u m s [ i ] nums[i] nums[i] 的点数。之后，你必须删除 所有 等于 n u m s [ i ] − 1 nums[i] - 1 nums[i]−1 和 nums[i] + 1 的元素。

开始你拥有

个点数。返回你能通过这些操作获得的最大点数。

题目描述

在这里插入图片描述

基本思路

1. 问题定义:

在这个问题中，我们有一个数组

，每个元素代表一个数字。你可以选择删除某个数字

，并获得

点数。然而，每当你删除一个数字

，与

相邻的数字

和

也会从数组中删除。问题要求的是：你通过删除数字获得的最大点数是多少?

2. 理解问题和递推关系:

这个问题类似于"打家劫舍"问题，可以转化为一个动态规划问题。每次删除某个数字时，你既获得了它的值，也会让相邻的数字无法再被选择。因此，可以把问题转化为：每个数

要么选择，要么跳过。

我们将问题理解为两个选择:

1. 选择删除某个数字

：那么你会获得

出现的总值

*出现次数，同时不能再选择

和

。

1. 不选择删除某个数字

：那么你可以选择去考虑删除其他数字。

为了将问题转化成打家劫舍的形式:

1. 我们可以对

进行预处理，统计每个数

的出现次数，然后构建一个数组

，其中

出现次数。

1. 现在，问题转化为：给定一个数组

，从中选择不相邻的数，使得获得的总和最大。这就是"打家劫舍"问题的典型形式。

3. 解决方法:

1. 预处理：首先统计

中每个数字的出现次数，并构建

，即

出现次数。

1. 递推公式：我们使用动态规划来解决该问题，设

表示前

个数字的最大点数。那么：

解释:

表示我们不删除数字

，因此直接继承前面的最大值。

表示我们删除了数字

，因此需要加上

，同时要跳过

。

1. 边界条件:

• 如果数组为空，直接返回

。

• 如果数组只有一个元素，那么返回该元素对应的

值。

4. 进一步优化:

在上述方法中，我们使用了一个数组

来保存每个位置的最大点数。但实际上，

只依赖于

和 dp[i-2]，因此可以通过使用两个变量来优化空间复杂度，从

降低到

。

• 时间复杂度：

，因为我们需要遍历数组构建

，以及进行动态规划。

• 空间复杂度：通过优化后可以降低到

，只需要常量空间保存前两个状态。

5. 小总结:

• 问题核心：通过删除某个数获得它的总值，并且不能删除与它相邻的数。这个问题转化为典型的动态规划问题。
• 动态规划：通过计算每个数出现的总值

，将问题简化为选择不相邻的数求最大和的问题。

• 优化：使用两个变量保存前两个状态，减少空间消耗。

以上就是删除并获得点数问题的基本思路。

代码实现

Python3代码实现

class Solution:
    def deleteAndEarn(self, nums: list[int]) -> int:
        if not nums:
            return 0
        
        # 统计每个数字的总收益
        max_num = max(nums)
        earn = [0] * (max_num + 1)
        for num in nums:
            earn[num] += num
        
        # 使用动态规划来解决打家劫舍问题
        prev2, prev1 = 0, 0
        
        for i in range(len(earn)):
            current = max(prev1, prev2 + earn[i])
            prev2 = prev1
            prev1 = current
        
        return prev1

Python 代码解释

1. 边界条件：如果

为空，直接返回

。

1. 统计：我们遍历

，构建

，其中

出现次数。

1. 动态规划：通过

和

来存储前两个状态的最大值，然后根据递推公式依次更新，最终返回

即为最大值。

C++代码实现

class Solution:
    def deleteAndEarn(self, nums: list[int]) -> int:
        if not nums:
            return 0
        
        # 统计每个数字的总收益
        max_num = max(nums)
        earn = [0] * (max_num + 1)
        for num in nums:
            earn[num] += num
        
        # 使用动态规划来解决打家劫舍问题
        prev2, prev1 = 0, 0
        
        for i in range(len(earn)):
            current = max(prev1, prev2 + earn[i])
            prev2 = prev1
            prev1 = current
        
        return prev1

C++ 代码解释

1. 边界条件：如果

为空，直接返回

。

1. 统计：构建

数组，存储每个数字的总收益。

1. 动态规划：使用两个变量

和

来分别存储前两个状态的最大收益，遍历数组

，最终返回

。

总结:

• 动态规划是解决此类问题的核心，将删除数字及其邻居的问题转化为典型的选择不相邻数的问题。
• 优化空间：通过使用常量空间，减少了数组存储的开销，使得算法在时间和空间上都更高效。