问题描述
给定一个二维矩阵，表示迷宫，每个格子表示一个房间，骑士在左上角，公主在右下角，每个单元格中的数字表示骑士进入房间需要消耗的健康值（用负数进行表示）或获得补充的健康值（用正数进行表示），骑士每次只能向右或向做进入下一个房间，骑士最小的健康值为 1，如果骑士健康值低于 1 ，则营救失败。要求找出骑士到达公主位置的路径中，骑士的初始健康值的最小值。题目链接：**点我**
样例输入输出
输入：[[-2,-3,3],[-5,-10,1],[10,30,-5]]
输出：7
输入：[[ 100 ]]
输出：1
问题解法
此解法参考：https://leetcode-cn.com/problems/dungeon-game/solution/di-xia-cheng-you-xi-by-leetcode-solution/，主要是使用动态规划，并且是从右下角开始向左上角进行遍历计算。用 cost[i][j] 表示从位置 [i, j] 到右下角位置所需的最小初始化的值，则 cost[i][j] 的取值是右边的路径和下边路径消耗健康值的最小值。在同一路径下，从上个房间到当前房间，计算当前房间所需的最小健康值的公式为：max(1, 上个房间所需的最小初始化健康值 - 当前房间的值)。代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| class Solution
{
public int calculateMinimumHP(int[][] dungeon)
{
int row = dungeon.length;
int col = dungeon[0].length;
int[][] cost = new int[row][col];
cost[row - 1][col - 1] = calcCost(1, dungeon[row - 1][col - 1]);
for (int i = row - 2; i >= 0; i--)
{
cost[i][col - 1] = calcCost(cost[i + 1][col - 1], dungeon[i][col - 1]);
}
for (int j = col - 2; j >= 0; j--)
{
cost[row - 1][j] = calcCost(cost[row - 1][j + 1], dungeon[row - 1][j]);
}
for (int i = row - 2; i >= 0; i--)
{
for (int j = col - 2; j >= 0; j--)
{
cost[i][j] = Math.min(calcCost(cost[i + 1][j], dungeon[i][j]), calcCost(cost[i][j + 1], dungeon[i][j]));
}
}
return cost[0][0];
}
private int calcCost(int frontCost, int currentCell)
{
if (currentCell >= frontCost)
{
return 1;
}
return frontCost - currentCell;
}
}
|
参考资料
https://leetcode-cn.com/problems/dungeon-game/solution/di-xia-cheng-you-xi-by-leetcode-solution/