🌕 174. 地下城游戏

难度: 🌕

问题描述

---

解法

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        // 思路：
        // 从右下角反推，得到到达左上角的最小体力值
        int row = dungeon.length;
        int col = dungeon[0].length;
        int[][] dp = new int[row][col]; // 到达 [i][j] 之前需要拥有的体力值，保证走完 [i][j] 后体力 > 0
        for(int i = row - 1; i >= 0; i --) {
            for(int j = col - 1; j >= 0; j --) {
                if(i == row - 1 && j == col - 1) {
                    dp[i][j] = Math.max(1, 1 - dungeon[i][j]);
                } else if(i == row - 1) {
                    // 最后一行，只能根据右边值进行计算
                    dp[i][j] = Math.max(1, dp[i][j + 1] - dungeon[i][j]);
                } else if(j == col - 1) {
                    // 最后一列，只能根据下边的值进行计算
                    dp[i][j] = Math.max(1, dp[i + 1][j] - dungeon[i][j]);
                } else {
                    // 根据 右 & 下 体力值计算，取最小值
                    dp[i][j] = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                    dp[i][j] = Math.max(1, dp[i][j]);
                }
            }
        }
        return dp[0][0];
    }
}

---

输出