174.地下城游戏

链接：174.地下城游戏
难度：Hard
标签：数组、动态规划、矩阵
简介：一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由  M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。

题解 1 - typescript

• 编辑时间：2020-07-12
• 执行用时：80ms
• 内存消耗：37.3MB
• 编程语言：typescript
• 解法介绍：dp[i][j]=i,j 坐标时需要的最小生命值，逆向推导 dp[0][0]。

function calculateMinimumHP(dungeon: number[][]): number {
  const n = dungeon.length;
  const m = dungeon[0].length;
  const dp = new Array(n + 1).fill(0).map(_ => new Array(m + 1).fill(Infinity));
  dp[n][m - 1] = dp[n - 1][m] = 1;
  for (let i = n - 1; i >= 0; --i) {
    for (let j = m - 1; j >= 0; --j) {
      dp[i][j] = Math.max(Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j], 1);
    }
  }
  return dp[0][0];
}