Java经典算法：地牢游戏

Java经典算法：地牢游戏

例：
-2（K）-3 3
-5 -10 1
10 30 -5（P）
Java解决方案
通过使用动态编程可以解决此问题。我们维护一个二维表。h [i] [j]是他进入（i，j）之前的最小健康值。h [0] [0]是答案的值。左侧是表格中的数字。
public int calculateMinimumHP(int[][] dungeon) {
int m = dungeon.length;
int n = dungeon[0].length;

//init dp table
int[][] h = new int[m][n];h[m - 1][n - 1] = Math.max(1 - dungeon[m - 1][n - 1], 1);//init last row
for (int i = m - 2; i >= 0; i--) {h[i][n - 1] = Math.max(h[i + 1][n - 1] - dungeon[i][n - 1], 1);
}//init last column
for (int j = n - 2; j >= 0; j--) {h[m - 1][j] = Math.max(h[m - 1][j + 1] - dungeon[m - 1][j], 1);
}//calculate dp table
for (int i = m - 2; i >= 0; i--) {for (int j = n - 2; j >= 0; j--) {int down = Math.max(h[i + 1][j] - dungeon[i][j], 1);int right = Math.max(h[i][j + 1] - dungeon[i][j], 1);h[i][j