关于前端:精读算法题-地下城游戏

6次阅读

共计 4775 个字符，预计需要花费 12 分钟才能阅读完成。

明天咱们看一道 leetcode hard 难度题目：地下城游戏。

恶魔们抓住了公主并将她关在了地下城 dungeon 的右下角。地下城是由 m x n 个房间组成的二维网格。咱们勇敢的骑士最后被安置在左上角的房间里，他必须穿过地下城并通过反抗恶魔来援救公主。

骑士的初始衰弱点数为一个正整数。如果他的衰弱点数在某一时刻降至 0 或以下，他会立刻死亡。

有些房间由恶魔守卫，因而骑士在进入这些房间时会失去衰弱点数（若房间里的值为负整数，则示意骑士将损失衰弱点数）；其余房间要么是空的（房间里的值为 0），要么蕴含减少骑士衰弱点数的魔法球（若房间里的值为正整数，则示意骑士将减少衰弱点数）。

为了尽快拯救公主，骑士决定每次只向右或向下挪动一步。

返回确保骑士可能援救到公主所需的最低初始衰弱点数。

留神：任何房间都可能对骑士的衰弱点数造成威逼，也可能减少骑士的衰弱点数，包含骑士进入的左上角房间以及公主被监禁的右下角房间。

输出：dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]

输入：7

解释：如果骑士遵循最佳门路：右 -> 右 -> 下 -> 下，则骑士的初始衰弱点数至多为 7。

挺像游戏的一道题，首先只能向下或向右挪动，所以每个格子能够由下面或右边的格子挪动而来，很天然想到能够用动静布局解决。

再想一想，该题必须遍历整个地下城而无奈取巧，因为最低衰弱点数无奈由部分数据算出，这是因为如果不把整个地下城走完，必定不晓得是否有更优路线。

二维迷宫用两个变量 i j 定位，其中 dp[i][j] 形容第 i 行 j 列所需的最低 HP。

但最低所需 HP 无奈推断出是否能继续前进，咱们还得晓得以后 HP 才行，比方：

// 从左到右走
3 -> -5 -> 6 -> -9

在数字 6 的地位所需最低 HP 是 3，但咱们必须晓得在 6 时勇者残余 HP 能力判断 -9 会不会间接导致勇者挂了，因而咱们将 dp[i][j] 后果定义为一个数组，第一项示意以后 HP，第二项示意初始所需最低 HP。

代码实现如下：

function calculateMinimumHP(dungeon: number[][]): number {// dp[i][j] 示意 i,j 地位 [以后 HP, 所需最低 HP]
  const dp = Array.from(dungeon.map(item => () => [0, 0]))
  // dp[i][j] = 所需最低 HP 最低 (dp[i-1][j], dp[i][j-1])
  dp[0][0] = [dungeon[0][0] > 0 ? 1 + dungeon[0][0] : 1,
    dungeon[0][0] > 0 ? 1 : 1 - dungeon[0][0]
  ]
  for (let i = 0; i < dungeon.length; i++) {for (let j = 0; j < dungeon[0].length; j++) {if (i === 0 && j === 0) {continue}

      const paths = []
      if (i > 0) {paths.push([i - 1, j])
      }
      if (j > 0) {paths.push([i, j - 1])
      }

      const pathResults = paths.map(path => {let leftMaxHealth = dp[path[0]][path[1]][0] + dungeon[i][j]
        // 残余 HP 大于 0 则无需刷新最低 HP，否则尝试刷新取最大值
        let lowestNeedHealth = dp[path[0]][path[1]][1]
        if (leftMaxHealth <= 0) {
          // 最低要求 HP 补上差价
          lowestNeedHealth += 1 - leftMaxHealth
          // 最低须要 HP 已补上，所以残余 HP 也变成了 1
          leftMaxHealth = 1
        }
        return [leftMaxHealth, lowestNeedHealth]
      })

      // 找到 pathResults 中 lowestNeedHealth 最小项
      let minLowestNeedHealth = Infinity
      let minIndex = 0
      pathResults.forEach((pathResult, index) => {if (pathResult[1] < minLowestNeedHealth) {minLowestNeedHealth = pathResult[1]
          minIndex = index
        }
      })

      dp[i][j] = [pathResults[minIndex][0], pathResults[minIndex][1]]
    }
  }

  return dp[dungeon.length - 1][dungeon[0].length - 1][1]
};

首先计算初始地位 dp[0][0]，因为只看这一个点，因而如果有恶魔，起码初始 HP 为能击败恶魔后本人剩 1 HP 就行了，如果房间是空的，至多本人 HP 得是 1（否则勇者进迷宫之前就挂了），如果有魔法球，那么初始 HP 为 1（一样避免进迷宫前挂了）。

初始 HP 稍有不同，如果房间是空的或者有恶魔，那打完恶魔之后最多剩 1 HP 最经济，所以此时 HP 初始值就是 1，如果有魔法球，那么一方面为了避免进入迷宫前本人就挂了，得有个初始 1 的 HP，魔法球又必须得吃，所以 HP 是 1 + 魔法球。

接着就是状态转移方程了，因为 dp[i][j] 能够由 dp[i-1][j] 或 dp[i][j-1] 挪动失去（留神 i 或 j 为 0 时的场景），因而咱们判断一下从哪条路过去的最低初始 HP 最低就行了。

如果进入以后房间后，房间是空的，有魔法球，或者以后 HP 能够战胜恶魔，则不影响最低初始 HP，如果以后 HP 不足以击败恶魔，则咱们把缺的 HP 给勇者在初始时补上，此时极限一些还剩 1 HP，失去一个最经济的后果。

而后咱们提交代码发现，无奈 AC！上面是一个典型挂掉的例子：

1   -3    3
0   -2    0
-3  -3   -3

咱们把 DP 两头过程输入，发现右下角的 5 大于最优答案 3.

[[ 2, 1], [1, 3], [4, 3]
  [2, 1], [1, 2], [1, 2]
  [1, 3], [1, 5], [1, 5]
]

察看发现，勇者先往右走到头，再往下走到头答案就是 3，问题出在 i=1,j=2 处，也就是两头行最右列的 [1, 2]。但从这一点来看，勇者从右边过去比从下面过去须要的初始 HP 少，因为右边是 [1, 2] 下面是 [4, 3]，但这导致了答案不是最优解，因为此时残余 HP 不够，右下角是一个攻打为 3 的恶魔，而如果此时咱们抉择了初始 HP 高一些的 [4, 3]，换来了更高的以后 HP，在不必补初始 HP 的状况就能把右下角恶魔干掉，整体是更划算的。

如果此时咱们在玩游戏，读读档也就能找到最优解了，但喜剧的是咱们在写一套算法， 咱们发现以后 DP 项竟然还可能由前面的值（攻击力为 3 的恶魔）决定！ 用业余的话来说就是有后效性导致无奈应用 DP。

咱们在判断每一步最优解时，其实有两个等同重要的因素影响判断，一个是初始起码所需 HP，它的重要度显而易见，咱们最终就心愿这个答案尽可能小；但还有以后 HP 呢，以后 HP 高意味着前面的路会更好走，但咱们如果不往后看，就不晓得前面是否有恶魔，天然也不晓得要不要留着高以后 HP 的路线，所以基本就无奈依据前一项下结论。

因为思考的因素太多了，咱们得换成游戏制作者的视角，假如作为游戏设计者，而不是玩家，你会真的从头玩一遍吗？如果真的要设计这种条件很极限的地下城，设计者必定从后果倒推啊，后果咱们勇者就只剩 1 HP 了，至于路上会遇到什么恶魔或者魔法球，反过来倒推就所有尽在把握了。所以咱们得采纳从右下角开始走的逆向思维。

为什么从后果倒推，DP 判断条件就没有后效性了呢？

先回顾一下从左上角登程的状况，为什么除了最低初始 HP 外还要记录以后 HP？起因是以后 HP 决定了以后房间的怪物勇者是否打得过，如果打不过，咱们得扩充最低初始 HP 让勇者能在仅剩 1 HP 的状况险胜以后房间的恶魔。 但这个以后 HP 值不仅要用来辅助计算最低初始 HP，它还有一个越大越好的性质，因为前面房间可能还有恶魔，得留一些 HP 预防危险 ，而 “ 最低初始 HP” 尽可能低与 “ 以后 HP” 尽可能高，这两个因素无奈同时思考。

那为什么从右下角，以终为始的思考就能够少判断一个条件了呢？首先最低初始 HP 咱们必定要判断的，因为答案要的就是这个，那以后 HP 呢？以后 HP 重要吗？不重要，因为你曾经援救到公主了，而且是以最低 HP 1 点的状态救到了公主，按故事路线逆着走，遇到恶魔房间，恶魔攻打是多少我就给你加多少初始 HP，遇到魔法球复原了我就给你扣对应初始 HP，总之能让你正好战败恶魔，魔法球补给你的 HP 我也扣掉，就能够了。外围区别是，此时以后 HP 曾经不会影响最低初始 HP 了，因为初始 HP 就是从头推的，咱们反着走地下城，每次实际上都是在判断这个点作为终点时的状态，所以与之前的门路无关。

代码很简略，如下：

function calculateMinimumHP(dungeon: number[][]): number {// dp[i][j] 示意 i,j 地位起码 HP
  const dp = Array.from(dungeon.map(item => () => [0, 0]))
  // 右下角起始 HP 1，遇到怪物加血，遇到魔法球扣血，实际上就是 -dungeon 计算
  const si = dungeon.length - 1
  const sj = dungeon[0].length - 1
  dp[si][sj] = dungeon[si][sj] > 0 ? 1 : 1 - dungeon[si][sj]
  for (let i = si; i >= 0; i--) {for (let j = sj; j >= 0; j--) {if (i === si && j === sj) {continue}

      const paths = []
      if (i < si) {paths.push([i + 1, j])
      }
      if (j < sj) {paths.push([i, j + 1])
      }

      const pathResults = paths.map(path => dp[path[0]][path[1]] - dungeon[i][j])
      // 选出最小 HP 作为 dp[i][j]，但不能小于 1
      dp[i][j] = Math.max(Math.min(...pathResults), 1)
    }
  }

  return dp[0][0]
};

逆向思维为什么就能缩小以后 HP（或者说门路和，或者说所有之前节点的影响）判断呢？我猜你大概率还是没彻底明确。因为这个思考十分要害，能够说是这道题 99% 的艰难所在，还是画个图解释一下:

上图是勇者失常探险的思路，上面是逆向（或公主救勇者）的思路。

该题很容易想到应用动静布局解决，但因为指标是求最低的初始衰弱点需要，所以依照勇者门路走的话，后续未摸索的门路会影响到指标，所以咱们须要从公主角度反向寻找勇者，才能够保障动静布局的每个判断点都只思考一个影响因素。