leetcode 174. 地下城游戏(Dungeon Game)
程序员文章站
2022-06-30 20:47:03
...
一时手抖把账号迁移到中国网站了。。。Discuss和Solution还没有,Submissions也很少,将就用吧。。
典型的动态规划:dp[i][j] = min(dp[i][j+1]-dungeon[i][j],dp[i+1][j]-dungeon[i][j])
先处理两条边界
从下往上从右往左遍历,返回dp[0][0]
public int calculateMinimumHP(int[][] dungeon) {
int m = dungeon.length;
int n = dungeon[0].length;
int dp[][] = new int[m][n];
dp[m-1][n-1] = dungeon[m-1][n-1] < 0 ? -1 * 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 i=n-2;i>=0;i--){
dp[m-1][i] = Math.max(dp[m-1][i+1] - dungeon[m-1][i],1);
}
for(int i = m-2;i >= 0;i--){
for(int j = n-2;j >= 0;j--){
int tempMin = Math.min(dp[i][j+1]-dungeon[i][j],dp[i+1][j]-dungeon[i][j]);
dp[i][j] = Math.max(1, tempMin);
}
}
return dp[0][0];
}
2ms,还行