☆打卡算法☆LeetCode 174. 地下城游戏 算法解析
☆打卡算法☆LeetCode 174. 地下城游戏 算法解析
一、题目
1、算法题目
“编写一个函数，来计算骑士能够拯救公主所需的最低初始健康点数。”
题目链接：
来源：力扣（LeetCode）
2、题目描述
一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
为了尽快到达公主，骑士决定每次只向右或向下移动一步。
编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。
例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。
说明:
- 骑士的健康点数没有上限。
- 任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。
示例 1：示例 2：二、解题
1、思路分析
这种寻找路径的题目，可以想到的就是使用动态规划，动态规划的重点就是找到子结构的规律。
首先，这是一个M * N的网格，每次只能向右或者向下移动一步，然后移动的时候要确保骑士在房间至少要有一点健康点数，直到骑士救出公主，也就是找一个可行的最小值路线。
提取一下有效信息：
- 骑士在每个房间至少有一点健康点，这样就不会死亡
- 每次移动只能向右或向下移动一步
- 确保骑士救出公主，遍历路线，找到最小值路线
这里有两种推导方式，一种是从前往后推，但是并不知道一开始的值是多少，假设开始设置了一个值，在推导过程中发现不满足条件就需要修改开始的值，这样很麻烦。
所以可以从后往前推，每个房间找到最优解，到起点就是要求的路线。
就比如这个例子：
从右下出发，那么往左走（5），往上走（2）：
那么很显然向上是最优解，那么向上后，再继续往左走（2），或往上走（-1）：
那么显然往上走是最优解，然后骑士健康点数要大于等于1，那么往上走的点数其实是1：
这样是不是就求出了一条可行的最优解了。
整理一下这个公式，对于这条路径dp[i][j]来说，只要求出dp[i][j+1]和dp[i+1][j]的最小值minn，当前格式的值为dungeon(i,j)，那么在坐标(i,j)的初始值只要达到minn-dungeon(i,j)即可，同时，初始值还必须大于等于1，那么方程：
dp[i][j] = max(min(dp[i+1][j],dp[i][j+1])-dungeon(i,j),1)
边界条件是当 i = n-1或者 j=m -1时，dp[i][j]转移需要用到dp[i][j+1]和dp[i+1][j]中有无效值，因此代码实现中给无效值赋值为极大值。
2、代码实现
代码参考：
class Solution {
public int calculateMinimumHP(int[][] dungeon) {
int n = dungeon.length, m = dungeon[0].length;
int[][] dp = new int[n + 1][m + 1];
for (int i = 0; i <= n; ++i) {
Arrays.fill(dp[i], Integer.MAX_VALUE);
}
dp[n][m - 1] = dp[n - 1][m] = 1;
for (int i = n - 1; i >= 0; --i) {
for (int j = m - 1; j >= 0; --j) {
int minn = Math.min(dp[i + 1][j], dp[i][j + 1]);
dp[i][j] = Math.max(minn - dungeon[i][j], 1);
}
}
return dp[0][0];
}
}
3、时间复杂度
时间复杂度：O(N X M)
其中N，M是给定矩阵的长宽。
空间复杂度：O(N X M)
其中N，M是给定矩阵的长宽。
三、总结
之所以要从终点向起点出发，是因为从起点到终点破坏了无后效性。
什么是无后效性，就是无法直接确定这条路径是否是唯一解，因为有两个重要程度相同的参数同时影响后续的决策。
这两个参数分别是：剩余血量与到达当前点所需要的最小初始化血量共同影响着后面一步的结果。