leetcode 174 地牢游戏(hard java 动态规划)

leetcode 174 地牢游戏(hard java 动态规划)

思路就是

dp[i][j]表示为了达到右下角，至少有多少血量能够在行走过程中至少保持一滴血

要从右下角开始向上推，因为只有在右下角知道最少还剩一滴血，然后向上推，最小血量 

java

class Solution {public int calculateMinimumHP(int[][] dungeon) {if(dungeon.length==0)return 0;int row=dungeon.length;int column=dungeon[0].length;int[][]dp = new int[row][column];dp[row-1][column-1]=Math.max(1,1-dungeon[row-1][column-1]);//先求右侧边for(int i=row-2;i>=0;i--){dp[i][column-1]=Math.max(1,dp[i+1][column-1]-dungeon[i][column-1]);}//求下侧边for(int j=column-2;j>=0;j--){dp[row-1][j]=Math.max(1,dp[row-1][j+1]-dungeon[row-1][j]);}//求中间for(int i=row-2;i>=0;i--){for(int j=column-2;j>=0;j--){//只能向左或者向上int dp_min=Math.min(dp[i+1][j],dp[i][j+1]);dp[i][j]=Math.max(1,dp_min-dungeon[i][j]);}}return dp[0][0];}
}