Every day a Leetcode
题目来源：3186. 施咒的最大总伤害
解法1：记忆化搜索
统计每个元素的出现次数，记到哈希表 cnt 中。将哈希表的 key 整理到数组 a 中，把 a 按照从小到大的顺序排序。
定义 dfs(i) 表示从 a[0] 到 a[i] 中选择，可以得到的伤害值之和的最大值。
考虑 a[i] 选或不选：
- 不选：问题变成从 a[0] 到 a[i−1] 中选择，可以得到的伤害值之和的最大值，即 dfs(i)=dfs(i−1)。
- 选：那么伤害值等于 a[i]−2 和 a[i]−1 的数不能选，问题变成从 a[0] 到 a[j−1] 中选择，可以得到的伤害值之和的最大值，其中 j 是最小的满足 a[j]≥a[i]−2 的数。那么 dfs(i)=dfs(j−1)+a[i]⋅cnt[a[i]]。
两种情况取最大值，得：dfs(i)=max(dfs(i−1),dfs(j−1)+a[i]⋅cnt[a[i]])。
递归边界：dfs(−1)=0。没有数可以选，伤害值之和为 0。
递归入口：dfs(n−1)，即答案。注意这里 n 是 a 的长度，即 power 中的不同元素个数。
代码：
#
# @lc app=leetcode.cn id=3186 lang=python3
#
# [3186] 施咒的最大总伤害
## @lc code=start
class Solution:def maximumTotalDamage(self, power: List[int]) -> int:cnt = Counter(power)a = sorted(cnt.keys())@cachedef dfs(i: int) -> int:if i < 0:return 0x = a[i]j = iwhile j > 0 and a[j - 1] >= x - 2:j -= 1res1 = dfs(i - 1) # 不选 a[i]res2 = dfs(j - 1) + x * cnt[x] # 选 a[i]return max(res1, res2)return dfs(len(a) - 1)
# @lc code=end
结果：
复杂度分析：
时间复杂度：O(nlogn)，其中 n 是 power 的长度。
空间复杂度：O(n)，其中 n 是 power 的长度。
