3186. Maximum Total Damage With Spell Casting

題目

A magician has various spells.

You are given an array power, where each element represents the damage of a spell. Multiple spells can have the same damage value.

It is a known fact that if a magician decides to cast a spell with a damage of power[i], they cannot cast any spell with a damage of power[i] - 2, power[i] - 1, power[i] + 1, or power[i] + 2.

Each spell can be cast only once.

Return the maximum possible total damage that a magician can cast.

題目連結

在一個陣列 power 中代表不同強度的咒語，題目的目標是要在其中選擇多個咒語進行施放，並且找到最大傷害的咒語組合，每個咒語只能被選擇一次，另一項限制是當選取某個強度為 $k$ 的咒語後，則強度 $k-2, k-1, k+1, k+2$ 的咒語都不能被使用。

思路

此題的複雜度比想像中高，即使將咒語進行排序後還是沒有一個很直觀的切入點可以下手，比較難找到 dp 裡關鍵的前後關係，因此參考 Editorial 中的關係式：

$$f(i)=\max_{power_j<power_i-2}f(j)+power_i\times count_i$$

首先先針對 power 中的數值進行記數，並將強度由小到大和出現次數以 tuple 的方式記錄在一個陣列裡面：

count = Counter(power)
pairs = []
for k in sorted(count.keys()):
    pairs.append((k, count[k]))

接下來準備一個長度是 len(pairs) 的矩陣，用來記錄使用幾種不同強度的咒語所能得到的最大傷害：

n = len(pairs)
dp = [0] * n

接下來進入到動態規劃的核心，我們會需要一個變數 mx 代表當下的最大傷害，也就是前面關係式中的

$$\max_{power_j<power_i-2}f(j)$$

其中 $j$ 則是一個指標來控制比較的位置。所以我們就可以從 0~n 進行遍歷，每一輪代表使用幾種不同強度的咒語，而在每一輪裡面用一個 while 迴圈來重複檢查在強度差距 2 以上的咒語當中何者造成的傷害比較大，最後再加上本身的傷害就完成最大傷害的更新。

mx = 0
j = 0 
for i in range(n):
    while j < i and pairs[j][0] < pairs[i][0] - 2:
        mx = max(mx, dp[j])
        j += 1
    dp[i] = mx + pairs[i][0] * pairs[i][1]

最後回傳 dp 的最大值即可。

Full Code

class Solution:
    def maximumTotalDamage(self, power):
        count = Counter(power)
        pairs = []
        for k in sorted(count.keys()):
            pairs.append((k, count[k]))
        n = len(pairs)
        dp = [0] * n
        mx = 0
        j = 0
        for i in range(n):
            while j < i and pairs[j][0] < pairs[i][0] - 2:
                mx = max(mx, dp[j])
                j += 1
            dp[i] = mx + pairs[i][0] * pairs[i][1]

        return max(dp)