订制型网站费用,东营人才网,甘肃温室大棚建设网站,收录情况动态规划—#740. 删除并获得点数 前言题目描述基本思路1. 问题定义:2. 理解问题和递推关系:3. 解决方法:4. 进一步优化:5. 小总结: 代码实现Python3代码实现Python 代码解释C代码实现C 代码解释 总结: 前言
给你一个整数数组 n u m s nums nums #xff0c;你可以对它进行一… 动态规划—#740. 删除并获得点数 前言题目描述基本思路1. 问题定义:2. 理解问题和递推关系:3. 解决方法:4. 进一步优化:5. 小总结: 代码实现Python3代码实现Python 代码解释C代码实现C 代码解释 总结: 前言
给你一个整数数组 n u m s nums nums 你可以对它进行一些操作。
每次操作中选择任意一个 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$ 的元素。
开始你拥有 0 0 0 个点数。返回你能通过这些操作获得的最大点数。
题目描述 基本思路
1. 问题定义:
在这个问题中我们有一个数组 n u m s [ ] nums[] nums[]每个元素代表一个数字。你可以选择删除某个数字 x x x 并获得 x x x 点数。然而每当你删除一个数字 x x x 与 x x x 相邻的数字 x − 1 x-1 x−1 和 x 1 x1 x1 也会从数组中删除。问题要求的是你通过删除数字获得的最大点数是多少?
2. 理解问题和递推关系:
这个问题类似于打家劫舍问题可以转化为一个动态规划问题。每次删除某个数字时你既获得了它的值也会让相邻的数字无法再被选择。因此可以把问题转化为每个数 x x x 要么选择要么跳过。
我们将问题理解为两个选择:
选择删除某个数字 x x x 那么你会获得 x x x 出现的总值 x x x *出现次数同时不能再选择 x − 1 x-1 x−1 和 x 1 x1 x1 。不选择删除某个数字 x x x 那么你可以选择去考虑删除其他数字。
为了将问题转化成打家劫舍的形式:
我们可以对 n u m s [ ] nums[] nums[] 进行预处理统计每个数 x x x 的出现次数然后构建一个数组 e a r n [ ] earn[] earn[]其中 e a r n [ x ] x ∗ earn [x]x * earn[x]x∗ 出现次数。现在问题转化为给定一个数组 e a r n [ ] earn[] earn[]从中选择不相邻的数使得获得的总和最大。这就是打家劫舍问题的典型形式。
3. 解决方法:
预处理首先统计 n u m s [ ] nums[] nums[] 中每个数字的出现次数并构建 e a r n [ ] earn[] earn[]即 e a r n [ x ] x ∗ earn[ x ]\mathrm{x} * earn[x]x∗ 出现次数。递推公式我们使用动态规划来解决该问题设 d p [ i ] d p[i] dp[i] 表示前 i i i 个数字的最大点数。那么 d p [ i ] max ( d p [ i − 1 ] , d p [ i − 2 ] earn [ i ] ) d p[i]\max (d p[i-1], d p[i-2]\operatorname{earn}[i]) dp[i]max(dp[i−1],dp[i−2]earn[i])
解释: d p [ i − 1 ] dp[i-1] dp[i−1] 表示我们不删除数字 i i i因此直接继承前面的最大值。 d p [ i − 2 ] e a r n [ i ] dp[i-2] earn[i] dp[i−2]earn[i] 表示我们删除了数字 i i i因此需要加上 e a r n [ i ] earn[i] earn[i]同时要跳过 i − 1 i-1 i−1。
边界条件:
如果数组为空直接返回 0 0 0 。如果数组只有一个元素那么返回该元素对应的 e a r n earn earn 值。
4. 进一步优化:
在上述方法中我们使用了一个数组 d p [ ] d p[] dp[] 来保存每个位置的最大点数。但实际上 d p [ i ] d p[i] dp[i] 只依赖于 d p [ i − 1 ] d p[i-1] dp[i−1] 和 dp[i-2]因此可以通过使用两个变量来优化空间复杂度从 O ( n ) O(n) O(n) 降低到 O ( 1 ) O(1) O(1) 。
时间复杂度 O ( n ) O(n) O(n) 因为我们需要遍历数组构建 e a r n [ ] earn[] earn[]以及进行动态规划。空间复杂度通过优化后可以降低到 O ( 1 ) O(1) O(1) 只需要常量空间保存前两个状态。
5. 小总结:
问题核心通过删除某个数获得它的总值并且不能删除与它相邻的数。这个问题转化为典型的动态规划问题。动态规划通过计算每个数出现的总值 e a r n [ x ] earn[x] earn[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 prev1Python 代码解释
边界条件如果 n u m s [ ] nums[] nums[] 为空直接返回 0 0 0。统计我们遍历 n u m s [ ] nums[] nums[]构建 e a r n [ ] earn[] earn[]其中 e a r n [ x ] x ∗ earn[x] x * earn[x]x∗ 出现次数。动态规划通过 p r e v 2 prev2 prev2 和 p r e v 1 prev1 prev1 来存储前两个状态的最大值然后根据递推公式依次更新最终返回 p r e v 1 prev1 prev1 即为最大值。
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 prev1C 代码解释
边界条件如果 n u m s [ ] nums[] nums[] 为空直接返回 0 0 0。统计构建 e a r n [ ] earn[] earn[] 数组存储每个数字的总收益。动态规划使用两个变量 p r e v 2 prev2 prev2 和 p r e v 1 prev1 prev1 来分别存储前两个状态的最大收益遍历数组 e a r n [ ] earn[] earn[]最终返回 p r e v 1 prev1 prev1。 总结:
动态规划是解决此类问题的核心将删除数字及其邻居的问题转化为典型的选择不相邻数的问题。优化空间通过使用常量空间减少了数组存储的开销使得算法在时间和空间上都更高效。
