一、题目
1、审题
2、分析
只能向右、向下移动的王子，从左上角要到右下角救公主，每经过一个方格，可能获得血瓶加血量，或者碰到怪物减血量，当王子血量 < 1 时就挂了，为了能成功救得公主，求王子的最小的初始血量。
二、解答
1、思路：
方法一、
采用二维数组 dp[][] 的动态规划方法：
①、使用数组 hp[i][j] 存储王子在位置 i，j 时所需的最小血量；从右下角向左上角进行计算；
②、hp 大小比方格多一行、多一列用于方便进行计算；且 hp 最后一行、最后一列初始化为 Integer.max；
③、 NEED = Min(hp[i+1][j], hp[i][j+1]) - dungeon[i][j]; // 即 从下方或从右方到达 (i, j) 时的最小血量需要，
若 NEED <= 0, 则 hp[i][j] = 1,即可，否则， hp[i][j] = NEED;
public int calculateMinimumHP2(int[][] dungeon) {int M = dungeon.length;int N = dungeon[0].length;int[][] hp = new int[M + 1][N+1];for (int i = 0; i < M; i++) {hp[i][N] = Integer.MAX_VALUE;}for (int i = 0; i < N; i++) {hp[M][i] = Integer.MAX_VALUE;}hp[M][N-1] = 1;hp[M-1][N] = 1;for (int i = M - 1; i >= 0; i--) {for (int j = N - 1; j >= 0; j--) {int need = Math.min(hp[i + 1][j], hp[i][j + 1]) - dungeon[i][j];hp[i][j] = need <= 0 ? 1: need;}}return hp[0][0];}
方法二、
采用一维数组 dp[] 的动态规划方法：
也是从底部向上边进行计算，碰到边界情况要特殊处理。
public int calculateMinimumHP(int[][] dungeon) {int M = dungeon.length;int N = dungeon[0].length;int[] dp = new int[N + 1];dp[N] = 1;int health = 0;for (int i = M - 1; i >= 0; i--) {for (int j = N - 1; j >= 0; j--) {if(i == M - 1) // 处理最后一行 health = dp[j + 1] - dungeon[i][j];else if(j == N - 1) // 处理每一行的最后一列health = dp[j] - dungeon[i][j];else // 有下边、右边的元素health = Math.min(dp[j + 1], dp[j]) - dungeon[i][j];dp[j] = health <= 0 ? 1 : health;}}return dp[0];}
