LeetCode刷题系列-- 174. 地下城游戏

一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。

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

有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。

为了尽快到达公主，骑士决定每次只向右或向下移动一步。

编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。

例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。

-2 (K)    -3    3
-5    -10    1
10    30    -5 (P)

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/dungeon-game
 

大佬的链接：动态规划帮我通关了《魔塔》 :: labuladong的算法小抄

思路：

此题与前面的 64. 最小路径和 为同一类型题，但是也有不同。
定义二维数组 dp[][] ，dp[i][j] 表示从grid[i][j] 到右下角所需的最少血量。
设 grid 数组的行数为 rowLen, 列数为 colmLen

1. dp[i][j] 的值与 dp[i][j+1] 与 dp[i+1][j] 有关，选择两者中值最小的路继续走，
2.
  2.1) 若是 grid[i][j] 为负数，则 dp[i][j] = min(dp[i][j+1],dp[i+1][j]) - grid[i][j]
  2.2) 若是 grid[i][j] 为正数时，
          2.2.1) 若是 grid[i][j] >= min(dp[i][j+1],dp[i+1][j]), 那么dp[i][j] = 1 即可，
              即保证从其他位置到 grid[i][j] 后，血量值为1 即可，剩下血量值就由 grid[i][j] 来补充
          2.2.2) 若是 grid[i][j] < min(dp[i][j+1],dp[i+1][j]), 那么dp[i][j] =  min(dp[i][j+1],dp[i+1][j]) - grid[i][j],
                    即到达 grid[i][j] 时，其血量需要最小为 min(dp[i][j+1],dp[i+1][j]) - grid[i][j] 既可以，余下血量由 grid[i][j] 补充
具体步骤如下：
1. 初始化
  1.1 dp[rowLen-1][colmLen-1] = grid[rowLen-1][colmLen-1]>=0?1:-grid[rowLen-1][colmLen-1] + 1,
      若是 grid[rowLen-1][colmLen-1] 为正数，表示到达最右下角前其血量至少为1即可；若是 grid[rowLen-1][colmLen-1] 为负数，表示到达最右下角前其血量至少为比扣除血量大 1 即可
  1.2 求解 dp[rowLen-1][j]
      dp[rowLen-1][j] = dp[rowLen-1][j+1] - grid[rowLen-1][j]
          若是 dp[rowLen-1][j] <=0 ，则 dp[rowLen-1][j] = 1 ，说明 grid[rowLen-1][j] 的补血量够大，所以到达该节点时，血量为 1 就够用了
  1.3 求解 dp[i][colmLen-1]
         dp[i][colmLen-1] = dp[i+1][colmLen-1] - grid[i][colmLen-1]
         若是 dp[i][colmLen-1] <=0 ，则 dp[i][colmLen-1] = 1 ，说明 grid[i][colmLen-1] 的补血量够大，所以到达该节点时，血量为 1 就够用了
2. 状态转移方程：
  对于dp[i][j]
      dp[i][j] = min(dp[i+1][j],dp[i][j]) = grid[i][j]，
      2.1) 如果 dp[i][j] <= 0 , dp[i][j] = 1, 说明grid[i][j] 的补血量足够大，所以到达该节点时，血量为 1 就够用了
3. 返回dp[0][0]

java：

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
                  int rowLen = dungeon.length;
        int colmLen = dungeon[0].length;
        // dp[i][j] 表示从 grid[i][j] 到右下角所需的最少血量
        int[][] dp = new int[rowLen][colmLen];
 
        dp[rowLen - 1][colmLen - 1] = dungeon[rowLen - 1][colmLen - 1] >= 0 ? 1 : -dungeon[rowLen - 1][colmLen - 1] + 1;
        // 1. 初始化
        for (int i = rowLen - 2; i >= 0; i--) {
            dp[i][colmLen - 1] = dp[i + 1][colmLen - 1] - dungeon[i][colmLen - 1];
            if (dp[i][colmLen - 1] <= 0) {
                dp[i][colmLen - 1] = 1; // 说明 grid[i][colmLen - 1] 的补血量够大，所以到达该节点时，血量为 1 就够用了
            }
        }
        for (int j = colmLen - 2; j >= 0; j--) {
            dp[rowLen - 1][j] = dp[rowLen - 1][j + 1] - dungeon[rowLen - 1][j];
            if (dp[rowLen - 1][j] <= 0) {
                dp[rowLen - 1][j] = 1; // 说明 grid[rowLen-1][j] 的补血量够大，所以到达该节点时，血量为 1 就够用了
            }
        }
        
        // 2. 状态转移方程
        for (int i = rowLen - 2; i >= 0; i--) {
            for (int j = colmLen - 2; j >= 0; j--) {
                dp[i][j] = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                if(dp[i][j]<=0) {
                    dp[i][j] = 1; // 说明 grid[i][j] 的补血量够大，所以到达该节点时，血量为 1 就够用了
                }
            }
        }
        return dp[0][0];
    }
}