| 题目链接 | 740. 删除并获得点数 |
|---|---|
| 思路 | 动态规划-打家劫舍-变体 |
| 题解链接 | 官方题解 |
| 关键点 | 优化版本：排序后，分段获取“连续子序列”的“打家劫舍值”后进行加和 |
| 时间复杂度 | \(O(\#{\text{nums}}+\max\text{nums})\)或\(O(n)\)（优化版本） |
| 空间复杂度 | \(O(\max\text{nums})\)或\(O(n)\)（优化版本） |
代码实现：
class Solution:
def deleteAndEarn(self, nums: List[int]) -> int:
maxv = max(nums)
total = [0] * (maxv+1)
for val in nums:
total[val] += val
def rob(nums):
sz = len(nums)
dp0 = dp1 = 0
for x in nums:
dp0, dp1 = dp1, max(dp1, dp0+x)
return dp1
return rob(total)
代码实现（优化版本）：
class Solution:
def deleteAndEarn(self, nums: List[int]) -> int:
def rob(nums):
sz = len(nums)
dp0 = dp1 = 0
for x in nums:
dp0, dp1 = dp1, max(dp1, dp0+x)
return dp1
n = len(nums)
answer = 0
nums.sort()
total = [nums[0]]
for i in range(1, n):
val = nums[i]
if val == nums[i-1]:
total[-1] += val
elif val == nums[i-1]+1:
total.append(val)
else:
answer += rob(total)
total = [val]
answer += rob(total)
return answer