3186. 施咒的最大总伤害

Problem: 3186. 施咒的最大总伤害

思路

看到题目有数值排列，以及限制在power[i]附近两个数，首先我们可以自然地想到要先排序。

接着，相同数值应该被归并到一起，我们创建一个数组来存储它，并创建另一个数组来存储相同数值的和。

然后，从题意可以看到，选择一个咒语，相差两个伤害值以内的咒语就不能使用，这相当于两者二选一，而选择是动态规划的拿手领域，顺其自然可以想到用dp求解。

我们设dp[i][j]为截止到第i小伤害值时的最大总伤害，j为1表示选择i，为1则表示不选择，由此我们可以列出状态转移方程，详见代码。

dp的一个经典应用就是第i个元素选择和不选择，分为两种状态。

复杂度

• 时间复杂度: $O(n)$
• 空间复杂度: $O(n)$

Code

class Solution {
    public long maximumTotalDamage(int[] power) {
        long ans = 0;
        Arrays.sort(power);
        int n = power.length;
        long dp[][] = new long[n][2];
        long a[] = new long[n];
        int b[] = new int[n];
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            int start = i;
            b[cnt] = power[start];
            a[cnt] = power[start];
            while (i < n - 1 && power[i + 1] == power[i]) {
                a[cnt] += power[i + 1];
                i++;
            }
            cnt++;
        }
        dp[0][1] = a[0];
        for (int i = 1; i < cnt; i++){
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
            if (i >= 2 && b[i] - 2 == b[i - 2]) {
                dp[i][1] = dp[i - 2][0] + a[i];
            } else if (b[i] - 1 == b[i - 1] || b[i] - 2 == b[i - 1]){
                dp[i][1] = dp[i - 1][0] + a[i];
            } else {
                dp[i][1] = dp[i][0] + a[i];
            }
        }
        return Math.max(dp[cnt - 1][0], dp[cnt - 1][1]);
    }
}