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];
}
}
