3186. Maximum Total Damage With Spell Casting

Leetcode link

题目简介

本题给我们一个数组 power，数组的元素代表能够造成的伤害

题目限制我们如果我们输出了 power[i] 的伤害，则在 power[i]-2 ~ power[i]+2 范围内的其他伤害就无效了（注意如果有 n 个 power[i] 的伤害，我们是可以造成 power[i] * n 的伤害的

题目让我们求出我们所能打出的最高伤害是多少

解题思路

首先我们了解到，是否能打出伤害只跟伤害的值本身有关系，跟顺序无关，所以我们可以先对 power 升序排序

其次，这种累进的题目大多在考我们对于动态规划的理解，我们首先需要知道每个伤害之间的关系

假设我们有个数组 dp，它的元素代表了当前的 power 所能打出的最大伤害

接下来我们需要考虑如何构建这个数组 dp

在伤害最大化的前提，我们首选对最大的伤害 power[max] 分析一波，我们有两种选择：打出该伤害；不打出该伤害

在打出该伤害的情况下：

• 当前伤害 = power[max] * n（n 为伤害出现的次数）

• 其余伤害 = dp[j]（j 为小于 power[i]-2 的伤害中最大的那一个）

• 我们取和：power[max] * n + dp[j]

在不打出该伤害的情况下：

• 当前伤害 = 0
• 其余伤害 = dp[max - 1]
• 取和：dp[max - 1]

如果我们要伤害最大化，则对 max 来说，我们需要 dp[max] = max(dp[max - 1], power[max] * n + dp[j])

如此一来 dp[dp.length - 1] 就会是我们的答案

但是我们还需要考虑到这个动态规划的入口，也就是我们要求 dp[i] 的时候，dp[i-1] 不能是 undefined

所以我们的 dp 数组长度需要是 power 数组去重之后的长度 + 1

Javascript

/**
 * @param {number[]} power
 * @return {number}
 */
var maximumTotalDamage = function (power) {
      // { power[i]: count(power[i]) }
    const map = new Map()
    power.forEach(p => {
        map.set(p, (map.get(p) || 0) + 1)
    })
      // deduplication the power
    const uniquePower = Array.from(map.keys()).sort((a, b) => a - b)
    const len = uniquePower.length
    const dp = new Array(len + 1).fill(0)


    for (let i = 0; i < len; i++) {
          // if choose power[i], count the current power
        const totalPower = uniquePower[i] * map.get(uniquePower[i])
        const idx = lowerBound(uniquePower, uniquePower[i] - 2)
        dp[i + 1] = Math.max(totalPower + dp[idx], dp[i])
    }

    return dp[len]
};

const lowerBound = (arr, target) => {
    let left = 0
    let right = arr.length
    while (left < right) {
        let mid = left + right >> 1
        if (arr[mid] >= target) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}