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

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

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

前言

给你一个整数数组 $n u m s$ ，你可以对它进行一些操作。

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

开始你拥有 $0$ 个点数。返回你能通过这些操作获得的最大点数。

题目描述

在这里插入图片描述

基本思路

1. 问题定义:

在这个问题中，我们有一个数组 $n u m s []$ ，每个元素代表一个数字。你可以选择删除某个数字 $x$ ，并获得 $x$ 点数。然而，每当你删除一个数字 $x$ ，与 $x$ 相邻的数字 $x - 1$ 和 $x + 1$ 也会从数组中删除。问题要求的是：你通过删除数字获得的最大点数是多少?

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

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

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

选择删除某个数字 $x$ ：那么你会获得 $x$ 出现的总值 $x$ *出现次数，同时不能再选择 $x - 1$ 和 $x + 1$ 。
不选择删除某个数字 $x$ ：那么你可以选择去考虑删除其他数字。

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

我们可以对 $n u m s []$ 进行预处理，统计每个数 $x$ 的出现次数，然后构建一个数组 $e a r n []$ ，其中 $e a r n [x] = x *$ 出现次数。
现在，问题转化为：给定一个数组 $e a r n []$ ，从中选择不相邻的数，使得获得的总和最大。这就是"打家劫舍"问题的典型形式。

3. 解决方法:

预处理：首先统计 $n u m s []$ 中每个数字的出现次数，并构建 $e a r n []$ ，即 $]=\mathrm{x} *$ 出现次数。
递推公式：我们使用动态规划来解决该问题，设 $d p [i]$ 表示前 $i$ 个数字的最大点数。那么：

$p[i]=\max (d p[i-1], d p[i-2]+\operatorname{earn}[i])$

解释:

$d p [i - 1]$ 表示我们不删除数字 $i$ ，因此直接继承前面的最大值。
$d p [i - 2] + e a r n [i]$ 表示我们删除了数字 $i$ ，因此需要加上 $e a r n [i]$ ，同时要跳过 $i - 1$ 。

边界条件:

如果数组为空，直接返回 $0$ 。
如果数组只有一个元素，那么返回该元素对应的 $e a r n$ 值。

4. 进一步优化:

在上述方法中，我们使用了一个数组 $d p []$ 来保存每个位置的最大点数。但实际上， $d p [i]$ 只依赖于 $d p [i - 1]$ 和 dp[i-2]，因此可以通过使用两个变量来优化空间复杂度，从 $O (n)$ 降低到 $O (1)$ 。

时间复杂度： $O (n)$ ，因为我们需要遍历数组构建 $e a r n []$ ，以及进行动态规划。
空间复杂度：通过优化后可以降低到 $O (1)$ ，只需要常量空间保存前两个状态。

5. 小总结:

问题核心：通过删除某个数获得它的总值，并且不能删除与它相邻的数。这个问题转化为典型的动态规划问题。
动态规划：通过计算每个数出现的总值 $e a r n [x]$ ，将问题简化为选择不相邻的数求最大和的问题。
优化：使用两个变量保存前两个状态，减少空间消耗。

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

代码实现

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, 0for i in range(len(earn)):current = max(prev1, prev2 + earn[i])prev2 = prev1prev1 = currentreturn prev1

Python 代码解释

边界条件：如果 $n u m s []$ 为空，直接返回 $0$ 。
统计：我们遍历 $n u m s []$ ，构建 $e a r n []$ ，其中 $e a r n [x] = x *$ 出现次数。
动态规划：通过 $p re v 2$ 和 $p re v 1$ 来存储前两个状态的最大值，然后根据递推公式依次更新，最终返回 $p re v 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, 0for i in range(len(earn)):current = max(prev1, prev2 + earn[i])prev2 = prev1prev1 = currentreturn prev1

C++ 代码解释

边界条件：如果 $n u m s []$ 为空，直接返回 $0$ 。
统计：构建 $e a r n []$ 数组，存储每个数字的总收益。
动态规划：使用两个变量 $p re v 2$ 和 $p re v 1$ 来分别存储前两个状态的最大收益，遍历数组 $e a r n []$ ，最终返回 $p re v 1$ 。