-
Notifications
You must be signed in to change notification settings - Fork 0
/
leetcode174.java
37 lines (30 loc) · 1.15 KB
/
leetcode174.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/*
health[i][j] = min{
dungeon[i][j] >= health[i+1][j] ? 1 : health[i+1][j] - dungeon[i][j],
dungeon[i][j] >= health[i][j+1] ? 1 : health[i][j+1] - dungeon[i][j]
}
*/
public class Solution {
public int calculateMinimumHP(int[][] dungeon) {
if (dungeon == null || dungeon.length == 0 || dungeon[0].length == 0)
return 0;
int row = dungeon.length;
int col = dungeon[0].length;
int[][] dp = new int[row][col];
dp[row-1][col-1] = Math.max(1-dungeon[row-1][col-1], 1);
for(int i = row-2; i >= 0; i--){
dp[i][col-1] = Math.max(dp[i+1][col-1] - dungeon[i][col-1],1);
}
for(int i = col-2; i >= 0; i--){
dp[row-1][i] = Math.max(dp[row-1][i+1] - dungeon[row-1][i],1);
}
for(int i = row-2; i >= 0; i--){
for(int j = col-2; j >= 0; j--){
int down = Math.max(dp[i+1][j] - dungeon[i][j], 1);
int right = Math.max(dp[i][j+1] - dungeon[i][j], 1);
dp[i][j] = Math.min(down,right);
}
}
return dp[0][0];
}
}