🌕 174. 地下城游戏
2022年10月10日
- algorithm
🌕 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];
}
}