| 题目链接 | 3186. 施咒的最大总伤害 |
|---|---|
| 思路 | 动态规划-打家劫舍（值域版）-简单变体 |
| 题解链接 | 【套路】值域打家劫舍（Python/Java/C++/Go） |
| 关键点 | 1. 排序 2. 对可选数字进行“打家劫舍” |
| 时间复杂度 | \(O(n\log n)\) |
| 空间复杂度 | \(O(n)\) |
代码实现：
class Solution:
def maximumTotalDamage(self, power: List[int]) -> int:
cnt = Counter(power)
cnt_sorted = sorted(cnt.keys())
@cache
def dfs(i: int):
if i < 0:
return 0
num = cnt_sorted[i]
j = i
while j and cnt_sorted[j-1] >= num-2:
j -= 1
return max(
dfs(i-1),
dfs(j-1) + num * cnt[num]
)
return dfs(len(cnt_sorted)-1)