网站开发和前端和数据媒体,河北综合网站建设系列,网站开发的人李海涛,做一个静态网站多少钱恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里#xff0c;他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0…恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下他会立即死亡。
有些房间由恶魔守卫因此骑士在进入这些房间时会失去健康点数若房间里的值为负整数则表示骑士将损失健康点数其他房间要么是空的房间里的值为 0要么包含增加骑士健康点数的魔法球若房间里的值为正整数则表示骑士将增加健康点数。
为了尽快解救公主骑士决定每次只 向右 或 向下 移动一步。
返回确保骑士能够拯救到公主所需的最低初始健康点数。
注意任何房间都可能对骑士的健康点数造成威胁也可能增加骑士的健康点数包括骑士进入的左上角房间以及公主被监禁的右下角房间。 示例 1 输入dungeon [[-2,-3,3],[-5,-10,1],[10,30,-5]]
输出7
解释如果骑士遵循最佳路径右 - 右 - 下 - 下 则骑士的初始健康点数至少为 7 。
示例 2
输入dungeon [[0]]
输出1解法一 回溯法
最直接暴力的方法就是做搜索了在每个位置无非就是向右向下两种可能然后去尝试所有的解然后找到最小的即可也就是做一个 DFS 或者说是回溯法。
//全局变量去保存最小值
int minHealth Integer.MAX_VALUE;public int calculateMinimumHP(int[][] dungeon) {//calculateMinimumHPHelper 四个参数//int x, int y, int health, int addHealth, int[][] dungeon//x, y 代表要准备到的位置x 代表是哪一列y 代表是哪一行//health 代表当前的生命值//addHealth 代表当前已经增加的生命值//初始的时候给加 1 点血addHealth 和 health 都是 1calculateMinimumHPHelper(0, 0, 1, 1, dungeon);return minHealth;
}private void calculateMinimumHPHelper(int x, int y, int health, int addHealth, int[][] dungeon) {//加上当前位置的奖励或惩罚health health dungeon[y][x];//此时是否需要加血加血的话就将 health 加到 1if (health 0) {addHealth addHealth Math.abs(health) 1;}//是否到了终点if (x dungeon[0].length - 1 y dungeon.length - 1) {minHealth Math.min(addHealth, minHealth);return;}//是否加过血if (health 0) {//加过血的话health 就变为 1if (x dungeon[0].length - 1) {calculateMinimumHPHelper(x 1, y, 1, addHealth, dungeon);}if (y dungeon.length - 1) {calculateMinimumHPHelper(x, y 1, 1, addHealth, dungeon);}} else {//没加过血的话health 就是当前的 healthif (x dungeon[0].length - 1) {calculateMinimumHPHelper(x 1, y, health, addHealth, dungeon);}if (y dungeon.length - 1) {calculateMinimumHPHelper(x, y 1, health, addHealth, dungeon);}}}然后结果是意料之中的会超时。 然后我们就需要剪枝将一些情况提前结束掉最容易想到的就是如果当前加的血已经超过了全局最小值那就可以直接结束不用进后边的递归。
if (addHealth minHealth) {return;
}
Copy
然后发现对于给定的 test case 并没有什么影响。
之所以超时就是因为我们会经过很多重复的位置比如
0 1 2
3 4 5
6 7 8
如果按 DFS第一条路径就是 0 - 1 - 2 - 5 - 8
然后通过回溯第二次判断的路径就会是 0 - 1 - 4 - 5 - ...
我们会发现它又会来到 5 这个位置
其他的也类似如果表格很大的话不停的回溯一些位置会经过很多次接下来就会想到用 map 去缓冲我们过程中求出的解key 话当然是 x 和 y 了value 呢存当前的 health 和 addhealth那第二次来到这个位置的时候我们并不能做什么比如举个例子。
第一次来到 (3,5) 的时候health 是 5addhealth 是 6。
第二次来到 (3,5) 的时候health 是 4addhealth 是 7我们什么也做不了我们并不知道未来它会走什么路。
因为走的路是由 health 和 addhealth 共同决定的此时来到相同的位置由于 health 和 addhealth 都不一样所以未来的路也很有可能变化所以我们并不能通过缓冲结果来剪枝。
我们最多能判断当 x、y、health 和 addhealth 全部相同的时候提前结束但这种情况也很少所以并不能有效的加快搜索速度。
这条路看起来到死路了我们换个思路去用动态规划。
动态规划的关键就是去定义我们的状态了这里直接将要解决的问题定义为我们的状态。
用 dp[i][j] 存储从起点 (0, 0) 到达 (i, j) 时候所需要的最小初始生命值。
到达 (i,j) 有两个点(i-1, j) 和 (i, j-1)。
接下来就需要去推导状态转移方程了。
* * 8 *
* 7 ! ?
? ? ? ?假如我们要求上图中 ! 位置的 dp假设之前的 dp 已经都求出来了。
那么 dp 是等于感叹号上边的 dp 还是等于它左边的 dp 呢选较小的吗
但如果 8 对应的当时的 health 是 100而 7 对应的是 5此时更好的选择应该是 8。
那就选 health 大的呗那 dp 不管了吗极端的例子假如此时的位置已经是终点了很明显我们应该选择从左边过来也就是 7 的位置过来之前的 health 并不重要了。
所以推到这里会发现因为我们有两个不确定的变量一个是 dp 也就是从起点 (0, 0) 到达 (i, j) 时候所需要的最小初始生命值还有一个就是当时剩下的生命值。
当更新 dp 的时候我们并不知道它应该是从上边下来还是从左边过来有利于到达终点的时候所需的初始生命值最小。
换句话讲依赖过去的状态并不能指导我们当前的选择因为还需要未来的信息。
所以到这里我再次走到了死胡同就去看 Discuss 了这里分享下别人的做法。
解法二 递归
看到 这里 评论区的一个解法。
所需要做的就是将上边动态规划的思路逆转一下。 ↓
→ *之前我们考虑的是当前这个位置它应该是从上边下来还是左边过来会更好些然后发现并不能确定。
现在的话看下边的图。
* → x
↓
y我们现在考虑从当前位置应该是向右走还是向下走这样我们是可以确定的。
如果我们知道右边的位置到终点的需要的最小生命值是 x下边位置到终点需要的最小生命值是 y。
很明显我们应该选择所需生命值较小的方向。
如果 x y我们就向右走。
如果 x y我们就向下走。
知道方向以后当前位置到终点的最小生命值 need 就等于 x 和 y 中较小的值减去当前位置上边的值。
如果算出来 need 大于 0那就说明我们需要 need 的生命值到达终点。
如果算出来 need 小于等于 0那就说明当前位置增加的生命值很大所以当前位置我们只需要给一个最小值 1就足以走到终点。
举个具体的例子就明白了。
如果右边的位置到终点的需要的最小生命值是 5下边位置到终点需要的最小生命值是 8。
所以我们选择向右走。
如果当前位置的值是 2然后 need 5 - 2 3所以当前位置的初始值应该是 3。
如果当前位置的值是 -3然后 need 5 - (-3) 8所以当前位置的初始值应该是 8。
如果当前位置的值是 10说明增加的生命值很多need 5 - 10 -5此时我们只需要将当前位置的生命值初始为 1 即可。
然后每个位置都这样考虑递归也就出来了。
递归出口也很好考虑 那就是最后求终点到终点需要的最小生命值。
如果终点位置的值是正的那么所需要的最小生命值就是 1。
如果终点位置的值是负的那么所需要的最小生命值就是负值的绝对值加 1。
public int calculateMinimumHP(int[][] dungeon) {return calculateMinimumHPHelper(0, 0, dungeon);
}private int calculateMinimumHPHelper(int i, int j, int[][] dungeon) {//是否到达终点if (i dungeon.length - 1 j dungeon[0].length - 1) {if (dungeon[i][j] 0) {return 1;} else {return -dungeon[i][j] 1;}}//右边位置到达终点所需要的最小值如果已经在右边界不能往右走了赋值为最大值int right j dungeon[0].length - 1 ? calculateMinimumHPHelper(i, j 1, dungeon) : Integer.MAX_VALUE;//下边位置到达终点需要的最小值如果已经在下边界不能往下走了赋值为最大值int down i dungeon.length - 1 ? calculateMinimumHPHelper(i 1, j, dungeon) : Integer.MAX_VALUE;//当前位置到终点还需要的生命值int need right down ? right - dungeon[i][j] : down - dungeon[i][j];if (need 0) {return 1;} else {return need;}
}当然还是意料之中的超时了。 不过不要慌还是之前的思想我们利用 map 去缓冲中间过程的值也就是 memoization 技术。
这个 map 的 key 和 value 就显而易见了key 是坐标 i,jvalue 的话就存当最后求出来的当前位置到终点所需的最小生命值也就是 return 前同时存进 map 中。
public int calculateMinimumHP(int[][] dungeon) {return calculateMinimumHPHelper(0, 0, dungeon, new HashMapString, Integer());
}private int calculateMinimumHPHelper(int i, int j, int[][] dungeon, HashMapString, Integer map) {if (i dungeon.length - 1 j dungeon[0].length - 1) {if (dungeon[i][j] 0) {return 1;} else {return -dungeon[i][j] 1;}}String key i j;if (map.containsKey(key)) {return map.get(key);}int right j dungeon[0].length - 1 ? calculateMinimumHPHelper(i, j 1, dungeon, map) : Integer.MAX_VALUE;int down i dungeon.length - 1 ? calculateMinimumHPHelper(i 1, j, dungeon, map) : Integer.MAX_VALUE;int need right down ? right - dungeon[i][j] : down - dungeon[i][j];if (need 0) {map.put(key, 1);return 1;} else {map.put(key, need);return need;}
}解法三 动态规划
其实解法二递归写完以后很快就能想到动态规划怎么去解了。虽然它俩本质是一样的但用动态规划可以节省递归压栈的时间直接从底部往上走。
我们的状态就定义成解法二递归中返回的值用 dp[i][j] 表示从 (i, j) 到达终点所需要的最小生命值。
状态转移方程的话和递归也一模一样只需要把函数调用改成取直接取数组的值。
因为对于边界的情况我们需要赋值为最大值所以数组的话我们也扩充一行一列将其初始化为最大值比如
奖惩数组
1 -3 3
0 -2 0
-3 -3 -3dp 数组
终点位置就是递归出口时候返回的值边界扩展一下
用 M 表示 Integer.MAXVALUE
0 0 0 M
0 0 0 M
0 0 4 M
M M M M然后就可以一行一行或者一列一列的去更新 dp 数组当然要倒着更新
因为更新 dp[i][j] 的时候我们需要 dp[i1][j] 和 dp[i][j1] 的值然后代码就出来了可以和递归代码做个对比。
public int calculateMinimumHP(int[][] dungeon) {int row dungeon.length;int col dungeon[0].length;int[][] dp new int[row 1][col 1];//终点所需要的值dp[row - 1][col - 1] dungeon[row - 1][col - 1] 0 ? 1 : -dungeon[row - 1][col - 1] 1;//扩充的边界更新为最大值for (int i 0; i col; i) {dp[row][i] Integer.MAX_VALUE;}for (int i 0; i row; i) {dp[i][col] Integer.MAX_VALUE;}//逆过来更新for (int i row - 1; i 0; i--) {for (int j col - 1; j 0; j--) {if (i row - 1 j col - 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];
}如果动态规划做的多的话必不可少的一步就是空间复杂度可以进行优化比如 5题10题53题72题 115 题 等等都已经用过了。
因为我们的 dp 数组在更新第 i 行的时候我们只需要第 i1 行的信息而 i2i3 行的信息我们就不再需要了我们我们其实不需要二维数组只需要一个一维数组就足够了。
public int calculateMinimumHP(int[][] dungeon) {int row dungeon.length;int col dungeon[0].length;int[] dp new int[col 1];for (int i 0; i col; i) {dp[i] Integer.MAX_VALUE;}dp[col - 1] dungeon[row - 1][col - 1] 0 ? 1 : -dungeon[row - 1][col - 1] 1;for (int i row - 1; i 0; i--) {for (int j col - 1; j 0; j--) {if (i row - 1 j col - 1) {continue;}dp[j] Math.min(dp[j], dp[j 1]) - dungeon[i][j];if (dp[j] 0) {dp[j] 1;}}}return dp[0];
}
