1、题目

image.png

2、分析

这道题需要通过反向动态规划来解决。
一般来说，遇到这种二维数组求最值的题目，我们dp[i][j]数组的含义是：从dp[0][0]到dp[i][j]，需要的最少生命值。但是这里，你连base case，也就是dp[0][[0], dp[0][....], dp[....][0]，都没法求出来。
这个时候，可以用反向思维来定义dp[i][j]数组：从dp[i][j]到终点dp[m][n]，所需要的最小生命值。
当i = m 和 j = n的时候，就是动态规划的base case

详细的思路参考：
https://labuladong.github.io/zgnb/3/17/28/

3、代码

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;
        int[][] dp = new int[m][n];
        //base case
        dp[m - 1][n - 1] = dungeon[m - 1][n - 1] >= 0 ? 1 : - dungeon[m - 1][n - 1] + 1;
        for(int i = m - 2; i >= 0; i--){
            int tmp = dp[i + 1][n - 1] - dungeon[i][n - 1];
            dp[i][n - 1] = tmp <= 0 ? 1 : tmp;
        }
        for(int i = n - 2; i >= 0 ; i--){
            int tmp = dp[m - 1][i + 1] - dungeon[m - 1][i];
            dp[m - 1][i] = tmp <= 0 ? 1 : tmp;
        }
        //反向动态规划
        for(int i = m - 2; i >= 0; i--){
            for(int j = n - 2; j >= 0; j--){
                int tmp = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                dp[i][j] = tmp <= 0 ? 1 : tmp;
            }
        }
        return dp[0][0];
    }
}