动态规划帮我通关了《魔塔》 :: labuladong的算法小抄 #983
Replies: 30 comments 6 replies
-
|
交作业~数组迭代自底向上如下 public int calculateMinimumHP(int[][] dungeon) {
int m = dungeon.length;
int n = dungeon[0].length;
int[][] dp = new int[m + 1][n + 1];
dp[m - 1][n - 1] = dungeon[m - 1][n - 1] < 0 ? -dungeon[m - 1][n - 1] + 1 : 1;
for (int i = m; i >= 0; i--) {
for (int j = n; j >= 0; j--) {
if (i == m || j == n) {
dp[i][j] = Integer.MAX_VALUE;
continue;
}
if (i == m - 1 && j == n - 1) {
continue;
}
int res = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
dp[i][j] = res <= 0 ? 1 : res;
}
}
return dp[0][0];
}状态压缩如下： public int calculateMinimumHPII(int[][] dungeon) {
int m = dungeon.length;
int n = dungeon[0].length;
int[] dp = new int[n + 1];
for (int i = m; i >= 0; i--) {
for (int j = n; j >= 0; j--) {
if (i == m || j == n) {
dp[j] = Integer.MAX_VALUE;
continue;
}
if (i == m - 1 && j == n - 1) {
dp[j] = dungeon[i][j] < 0 ? -dungeon[i][j] + 1 : 1;
continue;
}
int res = Math.min(dp[j], dp[j + 1]) - dungeon[i][j];
dp[j] = res <= 0 ? 1 : res;
}
}
return dp[0];
} |
Beta Was this translation helpful? Give feedback.
-
|
什么时候dp数组m需要+1 什么时候不需要 ，可以讲解下么 |
Beta Was this translation helpful? Give feedback.
-
|
这里扩大数组是为方便遍历吧。不然你构造[m][n]大小的数组，然后开两个循环先把边边填完，再开始填中间也是可以的。 |
Beta Was this translation helpful? Give feedback.
-
|
@ShermanQ 优秀！ |
Beta Was this translation helpful? Give feedback.
-
|
如果定一个 dp[i][j][2]：dp[i][j][0]代表[0][0]到[i][j]的血量，dp[i][j][1]:代表从[0][0]到[i][j]的最少血量 |
Beta Was this translation helpful? Give feedback.
-
|
@SunnyXiaoWei 不行，dp[i][j]选择dp[i-1][j]和dp[i][j-1]中需要最少血瓶的路径不一定是对的，如[[1,-3,3],[0,-2,0],[-3,-3,-3]]。这种办法只能通过40/45 |
Beta Was this translation helpful? Give feedback.
-
|
我也是卡在这个case😂 |
Beta Was this translation helpful? Give feedback.
-
这个代码的最核心的就是要从后往前，然后 要对base case 也就是最后一行和最后一列进行维护， 要和 m n 的 MAX_VALUE进行比较 ， （ps: 代码写的真tm的规范！！！👍） |
Beta Was this translation helpful? Give feedback.
-
|
dp数组的长度，有的时候是n，有的时候是n+1。什么时候用n，什么时候用n+1呢？这个地方一直很迷惑，希望大佬解答 |
Beta Was this translation helpful? Give feedback.
-
|
@nce3xin 因为数组索引是从 0 开始的， |
Beta Was this translation helpful? Give feedback.
-
|
@SunnyXiaoWei 并不行，一开始我也是这么做的，但是后面会发现你在选择的时候并不知道用血量转还是用到达该位置的最小初始值转，如果要做可能需要在你这个基础上再加一维存放来自左边和上方的那个三维数组，那就是4维了 |
Beta Was this translation helpful? Give feedback.
-
|
考虑两个场景， 备忘录借用入参 public int calculateMinimumHP(int[][] dungeon) {
// 倒着走，看一下最后在起点处， hp 最低是多少
for (int i = dungeon.length - 1; i >= 0; i--) {
for (int j = dungeon[i].length - 1; j >= 0; j--) {
if (i == dungeon.length-1 && j == dungeon[i].length - 1) {
dungeon[i][j] = dungeon[i][j]
} else if(i == dungeon.length-1) {
int right = dungeon[i][j+1];
dungeon[i][j] = right+ dungeon[i][j];
} else if(j == dungeon[i].length - 1) {
int down = dungeon[i+1][j] ;
dungeon[i][j] = down+ dungeon[i][j];
} else {
int right = dungeon[i][j+1] ;
int down = dungeon[i+1][j] ;
// 选hp多的那条路（也就是扣的少的那条路，因为hp都是负的或者0）
dungeon[i][j] = Math.max(right, down) + dungeon[i][j];
}
// 多余的 hp 没有意义，
// 追求的是 最小起始hp，不是到达hp，所以 hp 够用就行，多了没用，
// 考虑两个场景， 6 -> -5 ， 和 9 -> -5， 两个场景都可以活着，9比6并没有优势，所以应该优势抹平，置为0
if (dungeon[i][j] > 0) {
dungeon[i][j] = 0;
}
}
}
int min = dungeon[0][0];
if (min >= 0) {
return 1;
}
return -min+1;
} |
Beta Was this translation helpful? Give feedback.
-
|
JS版本 /**
* @param {number[][]} dungeon
* @return {number}
*/
var calculateMinimumHP = function (dungeon) {
const n = dungeon.length;
const m = dungeon[0].length;
const dp = Array(n + 1).fill(0).map(_ => Array(m + 1).fill(0));
// dp[i][j] 表示 从 (i,j) 到 终点 (n,m)所需要的最小血量
for (let i = 0; i <= n; i++) dp[i][m] = Number.MAX_SAFE_INTEGER;
for (let j = 0; j <= m; j++) dp[n][j] = Number.MAX_SAFE_INTEGER;
let res;
// 反着遍历 求0,0
for (let i = n-1; i >= 0; i--) {
for (let j = m-1; j >= 0; j--) {
if (i == n-1 && j == m-1) {
// 最后一个格子 是否会掉血？ 有血瓶或者啥都没有的时候 其实只需要留一滴血就行了
// 如果有掉血的怪物 那么最少血量就是怪物的伤害+1
dp[i][j] = dungeon[i][j] > 0 ? 1 : -dungeon[i][j] + 1;
} else {
// 计算 看看下发和右方 取最小的 减去当前格子的数值
res = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]
// 如果是正数(1- (-1)) 说明遇上了怪物 血量要是res才可以抗下 如果是负数 说明遇上了血瓶 只需要保证1点血即可
dp[i][j] = res <= 0 ? 1 : res;
}
}
}
return dp[0][0]
}; |
Beta Was this translation helpful? Give feedback.
-
|
Dont you get the same bugs if dp(0, 1) = 2, dp(1, 0) = 2?? I dont see how the second method can avoid the same situation... please help, I have been thinking about it for a week :( |
Beta Was this translation helpful? Give feedback.
-
if (i == 0 && j == 0) {
// 保证骑士落地不死就行了
return gird[i][j] > 0 ? 1 : -grid[i][j] + 1;
}各位大佬， |
Beta Was this translation helpful? Give feedback.
-
|
玩游戏的时候hp=0不就挂了吗哈哈 |
Beta Was this translation helpful? Give feedback.
-
11 行 DP 代码（空间压缩、自底向上）/**
* @param {number[][]} dungeon
* @return {number}
*/
var calculateMinimumHP = function (dungeon) {
const h = dungeon.length, w = dungeon[0].length;
let dp = new Array(w + 1).fill(Infinity);
for (let i = h - 1; i >= 0; --i) {
for (let j = w - 1; j >= 0; --j) {
if (i === h - 1 && j === w - 1) dp[j] = 0; // base case
dp[j] = Math.max(0, -dungeon[i][j] + Math.min(dp[j + 1], dp[j]));
}
}
return dp[0] + 1;
};
|
Beta Was this translation helpful? Give feedback.
-
自底向上的迭代方法(省去了数组越界判断） int calculateMinimumHP(int[][] grid) {
int m = grid.length, n = grid[0].length;
// dp[i][j]表示从grid[i][j]到grid[m-1][n-1]所需的最低血量
int[][] dp = new int[m+1][n+1];
// 初始化基本状态
// 省去数组越界的判断
for (int i = 0; i <= m; i++) {
dp[i][n] = Integer.MAX_VALUE;
}
for (int j = 0; j <= n; j++) {
dp[m][j] = Integer.MAX_VALUE;
}
// base case
dp[m-1][n-1] = grid[m-1][n-1] >= 0? 1: -grid[m-1][n-1] + 1;
// 进行循环
for (int i = m-1; i >= 0; i--) {
for (int j = n-1; j >= 0; j--) {
// 不要计算dp[m-1][n-1]的值
if (i == m-1 && j == n-1) {
continue;
}
// 状态转移方程
int tem = Math.min(dp[i][j+1], dp[i+1][j]) - grid[i][j];
dp[i][j] = tem > 0 ? tem: 1;
}
}
return dp[0][0];
} |
Beta Was this translation helpful? Give feedback.
-
Swift版本-迭代方式尝试一下 |
Beta Was this translation helpful? Give feedback.
-
|
外部初始化 使用二维 DP数组 class Solution {
public int calculateMinimumHP(int[][] dungeon) {
int m = dungeon.length;
int n = dungeon[0].length;
//dp[i][j] 从i ，j 位置到达 刚好能 到达终点的最低健康点数
int[][] dp = new int[m+1][n+1];
/*
表示如果出生在 最终节点位置
如果末尾位置有个血包，则至少需要1
如果末尾位置有个怪物，则至少需要 怪物攻击力 + 1 才能保证死不了
*/
dp[m-1][n-1] = dungeon[m-1][n-1] >= 0 ? 1 : -dungeon[m-1][n-1]+1;
for(int j = 0; j<=n;j++){
dp[m][j] = Integer.MAX_VALUE;
}
for(int i = 0; i<=m;i++){
dp[i][n] = Integer.MAX_VALUE;
}
for(int i = m-1 ; i>=0;i--){
for(int j = n-1;j>=0;j--){
if(i == m-1 && j==n-1){
continue;
}
/*
从右边 / 下边转移到 i j 选择其中较小的值
从i j 到 右边 / 下边是 加上 dungeon[i][j] 之后才会转移过去的， 所以从右边/下边 转移到i j 则需要 减去 dungeon[i][j]
*/
int temp = Math.min(dp[i+1][j],dp[i][j+1]) - dungeon[i][j];
//因为如果当前位置有 怪物 则至少保证 扣血之后 需要剩余1点
dp[i][j] = temp <= 0 ? 1 : temp;
}
}
return dp[0][0];
}
} |
Beta Was this translation helpful? Give feedback.
-
|
我这个挺容易理解的 |
Beta Was this translation helpful? Give feedback.
-
|
从后往前推导， 如果还是不理解的话 ， 可以反转一下 按照传统的 从前往后推导试试看 class Solution {
public int calculateMinimumHP(int[][] dungeon) {
int m = dungeon.length;
int n = dungeon[0].length;
//dp[i][j] 表示从 i-1 , j-1 开始 刚好到达 终点 至少需要的健康点数
//转换从 dp[i+1][j] dp[i][j+1] 转换到dp[i][j]
int[][] dp = new int[m+1][n+1];
//如果落地就是 终点 ， 需要保证勇士至少一滴血活着
if(dungeon[m-1][n-1] >=0){
dp[m-1][n-1] = 1;
}else{
dp[m-1][n-1] = -dungeon[m-1][n-1] + 1;
}
//最后一行与最后一列
//因为前面的是要选一个最小的 所以 都初始化成 MAX_VALUE;
dp[m][n] = Integer.MAX_VALUE;
for(int i = 0; i<= m; i++){
dp[i][n] = Integer.MAX_VALUE;
}
for(int j = 0; j<= n; j++){
dp[m][j] = Integer.MAX_VALUE;
}
for(int i = m-1 ; i>=0 ; i--){
for(int j = n-1; j>=0 ; j--){
//这个位置是终点位置 前面已经初始化过了
if(i== m-1 && j == n-1){
continue;
}
dp[i][j] = Math.min(dp[i+1][j],dp[i][j+1])-dungeon[i][j];
//至少保证剩一滴血
if(dp[i][j]<=0){
dp[i][j] = 1;
}
}
}
return dp[0][0];
}
} |
Beta Was this translation helpful? Give feedback.
-
|
C++ class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
int m = dungeon.size(), n = dungeon[0].size();
vector<int> dp(n);
dp[n - 1] = dungeon[m - 1][n - 1] >= 0 ? 1 : -dungeon[m - 1][n - 1] + 1;
for (int i = n - 2; i >= 0; --i) {
if (dp[i + 1] - dungeon[m - 1][i] > 0)
dp[i] = dp[i + 1] - dungeon[m - 1][i];
else
dp[i] = 1;
}
for (int i = m - 2; i >= 0; --i) {
if (dp[n - 1] - dungeon[i][n - 1] > 0)
dp[n - 1] = dp[n - 1] - dungeon[i][n - 1];
else
dp[n - 1] = 1;
for (int j = n - 2; j >= 0; --j) {
if (min(dp[j], dp[j + 1]) - dungeon[i][j] > 0)
dp[j] = min(dp[j], dp[j + 1]) - dungeon[i][j];
else
dp[j] = 1;
}
}
return dp[0];
}
}; |
Beta Was this translation helpful? Give feedback.
-
|
交个作业 public class leetcode_174 {
int calculateMinimumHP(int[][] grid){
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
dp[m-1][n-1] = grid[m-1][n-1] >= 0 ? 1 : -grid[m-1][n-1] + 1;
for (int i = m-2; i >= 0; i--) {
int res = dp[i+1][n-1] - grid[i][n-1];
dp[i][n-1] = res <= 0 ? 1 : res;
}
for (int i = n-2; i >= 0 ; i--) {
int res = dp[m-1][i+1] - grid[m-1][i];
dp[m-1][i] = res <= 0 ? 1 : res;
}
for (int i = m-2; i >= 0; i--) {
for (int j = n-2; j >= 0; j--) {
int res = Math.min(dp[i+1][j], dp[i][j+1]) - grid[i][j];
dp[i][j] = res <= 0 ? 1 : res;
}
}
return dp[0][0];
}
} |
Beta Was this translation helpful? Give feedback.
-
|
为什么都要用一个dp数组，不能直接在原数组上面修改数据吗？这样可以减小空间复杂度吧 |
Beta Was this translation helpful? Give feedback.
-
|
一样的，我只是为了逻辑清晰 |
Beta Was this translation helpful? Give feedback.
-
|
打卡打卡。 自底向上，DP table就要从右下角开始填起。 |
Beta Was this translation helpful? Give feedback.
-
|
递归版本 class Solution {
public int calculateMinimumHP(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
dp[m-1][n-1] = grid[m-1][n-1]>=1?1:-grid[m-1][n-1]+1;
for(int i=m-2; i>=0; i--) {
int t = dp[i+1][n-1]-grid[i][n-1];
dp[i][n-1] = t<=0? 1 : t;
}
for(int i=n-2; i>=0; i--) {
int t = dp[m-1][i+1] - grid[m-1][i];
dp[m-1][i] = t<=0? 1 : t;
}
for(int i=m-2; i>=0; i--) {
for(int j=n-2; j>=0; j--) {
int t = Math.min(dp[i][j+1], dp[i+1][j]) -grid[i][j];
dp[i][j] = t<=0?1:t;
}
}
return dp[0][0];
}
} |
Beta Was this translation helpful? Give feedback.
-
|
不对，是迭代，打错了 |
Beta Was this translation helpful? Give feedback.
-
|
能详细地说明下为什么反向，从终点开始往回找就能得到正确的答案吗？看不懂😂 |
Beta Was this translation helpful? Give feedback.
-
|
不愧是hard难度的题，我果然一开始陷入最小路径和的陷阱里。再次证明了dp的定义一定要能满足状态转移，如果不行就要倒回去思考dp定义了！ public int calculateMinimumHP(int[][] dungeon) {
int m = dungeon.length, n = dungeon[0].length;
int[][] dp = new int[m+1][n+1];
// base case
for (int i = 0; i <= m; i ++) {
dp[i][n] = Integer.MAX_VALUE;
}
for (int j = 0; j <= n; j ++) {
dp[m][j] = Integer.MAX_VALUE;
}
dp[m-1][n-1] = dungeon[m - 1][n - 1] < 0 ? 1 - dungeon[m - 1][n - 1] : 1; // 保证最低血量为正数
for (int i = m - 1; i >= 0; i --) {
for (int j = n - 1; j >= 0; j --) {
if (i == m - 1 && j == n - 1) continue;
int val = Math.min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j];
dp[i][j] = val <= 0 ? 1 : val; // 保证出生在[i,j]的最低血量为正数
}
}
return dp[0][0];
}降维压缩： public int calculateMinimumHP(int[][] dungeon) {
int m = dungeon.length, n = dungeon[0].length;
int[] dp = new int[n+1];
// base case
Arrays.fill(dp, Integer.MAX_VALUE); // 缺少这句会有小用例通不过
dp[n-1] = dungeon[m - 1][n - 1] < 0 ? 1 - dungeon[m - 1][n - 1] : 1;
for (int i = m - 1; i >= 0; i --) {
for (int j = n - 1; j >= 0; j --) {
if (i == m - 1 && j == n - 1) continue;
int val = Math.min(dp[j], dp[j+1]) - dungeon[i][j];
dp[j] = val <= 0 ? 1 : val;
}
}
return dp[0];
} |
Beta Was this translation helpful? Give feedback.
-
打卡（需要二刷） |
Beta Was this translation helpful? Give feedback.
-
var calculateMinimumHP = function(grid) {
const m = grid.length;
const n = grid[0].length;
const dp = new Array(m).fill().map(() => new Array(n).fill(0))
dp[m - 1][n -1] = grid[m - 1][n - 1] > 0 ? 1 : -grid[m - 1][n - 1] + 1;
// dp[i][j] 骑士到达 ij 最少需要的血量
// dp[i][j] = Math.min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]
for (let i = m - 1; i >= 0; i--) {
for (let j = n - 1; j >= 0; j--) {
if (i === m - 1 && j === n - 1) {
continue;
}
if (i === m - 1) {
dp[i][j] = dp[i][j + 1] - grid[i][j]
} else if (j === n - 1) {
dp[i][j] = dp[i + 1][j] - grid[i][j]
} else {
dp[i][j] = Math.min(dp[i + 1][j], dp[i][j + 1]) - grid[i][j]
}
dp[i][j] = dp[i][j] <= 0 ? 1 : dp[i][j];
}
}
return dp[0][0]
};压缩空间： var calculateMinimumHP = function(grid) {
const m = grid.length;
const n = grid[0].length;
const dp = new Array(n).fill(0)
dp[n - 1] = grid[m - 1][n - 1] > 0 ? 1 : -grid[m - 1][n - 1] + 1;
// dp[i][j] 骑士到达 ij 最少需要的血量
dp[i][j] = Math.min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]
for (let i = m - 1; i >= 0; i--) {
for (let j = n - 1; j >= 0; j--) {
if (i === m - 1 &&; j === n - 1) {
continue;
}
if (i === m - 1) {
dp[j] = dp[j + 1] - grid[i][j]
} else if (j === n - 1) {
dp[j] = dp[j] - grid[i][j]
} else {
dp[j] = Math.min(dp[j], dp[j + 1]) - grid[i][j]
}
dp[j] = dp[j] <= 0 ? 1 : dp[j];
}
}
Return DP[0]
}; |
Beta Was this translation helpful? Give feedback.
-
|
利用玩游戏的思维解决 class Solution {
int[][] memo;
//递归出栈找到小于0的位置
public int calculateMinimumHP(int[][] dungeon) {
int m = dungeon.length;
int n = dungeon[0].length;
memo = new int[m][n];
for (int[] a : memo) {
Arrays.fill(a, Integer.MAX_VALUE);
}
int val = dfs(dungeon, 0, 0, m, n);
return val < 0 ? -val : 1;
}
public int dfs(int[][] dungeon, int x, int y, int m, int n) {
//base case
//走进格子：至少需要一滴血
//走出格子：1.如果格子的血>=0,只需要走进的血即一滴血 2.格子的血<0,消耗的血+走进格子的血
if (x == m - 1 && y == n - 1) {
return dungeon[x][y] >= 0 ? -1 : dungeon[x][y] - 1;
}
if (x >= m || y >= n) {
return Integer.MIN_VALUE;
}
if (memo[x][y] != Integer.MAX_VALUE) {
return memo[x][y];
}
int xVal = dfs(dungeon, x + 1, y, m, n);
int yVal = dfs(dungeon, x, y + 1, m, n);
int max = Math.max(xVal, yVal);
int val = dungeon[x][y];
if (val < 0) {
//当前格子消耗血+走完后续消耗的血
memo[x][y] = val + max;
} else {
if (val + max >= 0) {
//当前格子走完后续格子都是大于0的，保证走进当前格子即可
memo[x][y] = -1;
} else if (val + max < 0) {
//当前格子走完后续格子需要的血
memo[x][y] = (val + max);
}
}
return memo[x][y];
}
} |
Beta Was this translation helpful? Give feedback.
-
|
dp table实现,还可继续状态压缩，在这里没有优化了 class Solution {
public int calculateMinimumHP(int[][] dungeon) {
return -dpArray(dungeon);
}
public int dpArray(int[][] dungeon) {
int m = dungeon.length;
int n = dungeon[0].length;
int[][] dp = new int[m + 1][n + 1];
Arrays.fill(dp[m], Integer.MIN_VALUE);
for (int i = 0; i <= m; i++) {
dp[i][n] = Integer.MIN_VALUE;
}
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
int val = dungeon[i][j];
int max = Math.max(dp[i + 1][j], dp[i][j + 1]);
//处理最后一个位置
max = max == Integer.MIN_VALUE ? -1 : max;
if (val + max < 0) {
dp[i][j] = val + max;
} else {
dp[i][j] = -1;
}
}
}
return dp[0][0];
}
} |
Beta Was this translation helpful? Give feedback.
and others
-
文章链接点这里：动态规划帮我通关了《魔塔》
评论礼仪 见这里，违者直接拉黑。
Beta Was this translation helpful? Give feedback.
All reactions