My code:
public class Solution {
public int calculateMinimumHP(int[][] dungeon) {
int row = dungeon.length;
int col = dungeon[0].length;
dungeon[row - 1][col - 1] = Math.max(1 - dungeon[row - 1][col - 1], 1);
for (int i = col - 2; i >= 0; i--) {
dungeon[row - 1][i] = Math.max(dungeon[row - 1][i + 1] - dungeon[row - 1][i], 1);
}
for (int i = row - 2; i >= 0; i--) {
dungeon[i][col - 1] = Math.max(dungeon[i + 1][col - 1] - dungeon[i][col - 1], 1);
}
for (int i = row - 2; i >= 0; i--) {
for (int j = col - 2; j >= 0; j--) {
int down = Math.max(dungeon[i + 1][j] - dungeon[i][j], 1);
int right = Math.max(dungeon[i][j + 1] - dungeon[i][j], 1);
dungeon[i][j] = Math.min(down, right);
}
}
return dungeon[0][0];
}
}
reference:
http://www.programcreek.com/2014/03/leetcode-dungeon-game-java/
从右下往左上扫描。
dp[i][j] 表示进入 (i, j) 这个房间之前应该拥有的最小血量，使得王子可以存活。
Anyway, Good luck, Richardo! -- 09/29/2016
