leetcode 174. Dungeon Game (地牢游戏）

leetcode 174. Dungeon Game (地牢游戏）

题意大致如下：
有个地牢，公主（P）被关在右下角格子里，骑士（K）会从左上角格子进入营救公主，骑士初始有一个血量。每个格子中可能有怪兽，会减掉骑士的血量（负数），也可能有药水，会增加骑士的血量（正数）。骑士的血量一旦减到0或者0以下，就会挂掉。问骑士能顺利营救公主所需要的初始血量。骑士每次只会向右边或者下面移动

需要注意的是在左上角的格子和右下角的格子，也就是骑士刚进入的格子和公主所在的格子也可能会减少血量。

思路：
从公主所在的格子倒推回初始的格子，
因为骑士每次只会向右边或者下边移动，所以只需要取右边和下边的较小值即可。
右边界的情况只需要看下边的格子，下边界只需要看右边的格子。

但是需要注意几点：

1. 骑士的血量一旦到达0或者0以下会挂掉，所以要保证每个格子的血量至少是1.
2. 营救到公主的最后一刻，即到达右下角的时候也要保证活着见到公主，所以初始化最后一格血量的时候要保证至少是1
3. 需要的血量也就是至少是1的血量 减去 地牢中的数字

    public int calculateMinimumHP(int[][] dungeon) {if(dungeon == null || dungeon.length == 0) {return 0;}int m = dungeon.length;int n = dungeon[0].length;int[][] dp = new int[m][n];//营救到公主的最后一刻也要保证血量至少是1dp[m-1][n-1] = Math.max(-dungeon[m-1][n-1] + 1, 1);//初始化右边界for(int i = m-2; i >= 0; i--) {dp[i][n-1] = Math.max(dp[i+1][n-1] - dungeon[i][n-1], 1);}//初始化下边界for(int j = n-2; j >= 0; j--) {dp[m-1][j] = Math.max(dp[m-1][j+1] - dungeon[m-1][j], 1);}for(int i = m-2; i >= 0; i--) {for(int j = n-2; j >= 0; j--) {//思路是取右边和下边的较小值，同时保证至少是1//但是为了减少计算量，取了简化版本//int right = Math.max(dp[i][j+1] - dungeon[i][j], 1);//int down = Math.max(dp[i+1][j] - dungeon[i][j], 1);//dp[i][j] = Math.min(right, down);dp[i][j] = Math.min(dp[i][j+1], dp[i+1][j]) - dungeon[i][j];dp[i][j] = Math.max(dp[i][j], 1);}}return dp[0][0];}