-
Notifications
You must be signed in to change notification settings - Fork 2
/
DungeonGame.java
60 lines (54 loc) · 1.98 KB
/
DungeonGame.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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
package src.java.hard.matrix;
import java.util.ArrayList;
import java.util.List;
public class DungeonGame {
// Backtracking - TLE
public int calculateMinimumHP(int[][] dungeon) {
List<Integer> list = new ArrayList<>();
list.add(dungeon[0][0]);
int ret = dfs(dungeon, 0, 0, list);
if (ret >= 0) return 1;
else return -ret+1;
}
private int dfs(int[][] dungeon, int m, int n, List<Integer> list) {
if (m==dungeon.length-1 && n==dungeon[m].length-1) {
int sum = 0, ret = 0;
for (int i=0; i<list.size(); i++) {
sum += list.get(i);
if (ret > sum) ret = sum;
}
return ret;
}
int max = Integer.MIN_VALUE;
int[][] dirs = {{0, 1}, {1, 0}};
for (int i=0; i<dirs.length; i++) {
int newM = m + dirs[i][0];
int newN = n + dirs[i][1];
if (newM < dungeon.length && newN < dungeon[0].length) {
list.add(dungeon[newM][newN]);
int curMin = dfs(dungeon, newM, newN, list);
list.remove(list.size()-1);
max = Math.max(max, curMin);
}
}
return max;
}
// DP solution
public int calculateMinimumHP2(int[][] dungeon) {
//dp[i][j] = minimum health level required to reach the princess when entering (i, j)
// dp[i][j] = max{min{dp[i-1][j], dp[i][j-1]} - dungeon[i][j], 0}
int m = dungeon.length;
int n = m == 0 ? 0 : dungeon[0].length;
int[][] dp = new int[m+1][n+1];
for(int i=0; i<=m; i++) dp[i][n] = Integer.MAX_VALUE;
for(int i=0; i<=n; i++) dp[m][i] = Integer.MAX_VALUE;
dp[m-1][n] = 0;
dp[m][n-1] = 0;
for (int i=m-1; i>=0; i--) {
for (int j=n-1; j>=0; j--) {
dp[i][j] = Math.max(Math.min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j], 0);
}
}
return dp[0][0]+1;
}
}