友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
3186. 施咒的最大总伤害
一个魔法师有许多不同的咒语。
给你一个数组 power，其中每个元素表示一个咒语的伤害值，可能会有多个咒语有相同的伤害值。
已知魔法师使用伤害值为 power[i] 的咒语时，他们就 不能 使用伤害为 power[i] - 2 ，power[i] - 1 ，power[i] + 1 或者 power[i] + 2 的咒语。
每个咒语最多只能被使用 一次 。
请你返回这个魔法师可以达到的伤害值之和的 最大值 。
示例 1：
输入：power = [1,1,3,4] 输出：6 解释： 可以使用咒语 0，1，3，伤害值分别为 1，1，4，总伤害值为 6 。
示例 2：
输入：power = [7,1,6,6] 输出：13 解释： 可以使用咒语 1，2，3，伤害值分别为 1，6，6，总伤害值为 13 。
提示：
-
1 <= power.length <= 105 -
1 <= power[i] <= 109
思路分析
有点懵逼！有点绕，需要把原始数组，按照伤害值转化成新的数组，这样就可以在新数组上，使用类似“打家劫舍”的套路来解题了。与“打家劫舍”套路不同的是，这里“选”的时候，前面被选择的项不是一个固定的项，是根据伤害条件选择出来的项。
\( f(i) = \max_{power_{j} < power_{i} - 2} f(j) + power_{i} \times count_{i} \)
-
一刷(暴力破解)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-01-09 20:11:43
*/
public long maximumTotalDamage(int[] power) {
// 统计每个伤害的个数
Map<Integer, Integer> cnt = new HashMap<>();
for (int p : power) {
cnt.merge(p, 1, Integer::sum);
}
int n = cnt.size();
int[] a = new int[n];
int i = 0;
for (Integer k : cnt.keySet()) {
a[i++] = k;
}
Arrays.sort(a);
long[] memo = new long[n];
Arrays.fill(memo, -1);
return dfs(a, cnt, memo, n - 1);
}
private long dfs(int[] a, Map<Integer, Integer> cnt, long[] memo, int index) {
if (index < 0) {
return 0;
}
if (memo[index] >= 0) {
return memo[index];
}
long result = dfs(a, cnt, memo, index - 1);
int x = a[index];
int j = index;
// 这里为什么是 j-1，而不是 j ？
while (j > 0 && a[j - 1] >= x - 2) {
j--;
}
result = Math.max(result, dfs(a, cnt, memo, j - 1) + x * cnt.get(x));
return memo[index] = result;
}