⚔ LeetCode | 174. Dungeon Game

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

Problem

LeetCode 174. Dungeon Game

Difficulty : Hard

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0’s) or contain magic orbs that increase the knight’s health (positive integers).

In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Write a function to determine the knight’s minimum initial health so that he is able to rescue the princess.

For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.

-2 (K) -3 3
-5 -10 1
10 30 -5 (P)

Note:

  • The knight’s health has no upper bound.
  • Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

Analysis

这是一个有 n*m 个格子的地牢，每个地牢会有陷阱或者血包，增加或者减少骑士的生命值。骑士需要从左上角的格子走到右下角的格子，期间生命值要保证大于 0。

我们需要做的就是求出骑士的最小生命值，保证他从左上角有一条路径可以安全到达右下角。

虽然这个题目看上去有点长，而且各种规则看上去也是有一点绕，但是本质上还是一道动态规划的题目。骑士每次只能向右或者向下移动，这就保证了骑士不会走回环，就有了固定的选择，这样就很容易找到最佳路径。

Approach 1

最直观的解法就是从左上角一直模拟走到右下角。但是这样的话需要同时规划最小的血量和当前骑士的血量，因为有些格子是加血的，那样如果骑士经过这个格子走到下一个格子的时候，可能并不需要增加生命值就可以通过。

但是这样又带来了另一个问题。我们对于一个格子，可以决定是从上面下来还是从左边过来，那么如果有一个格子的最大生命值比较小，而另一个格子的当前生命值比较大，那么我们应该选择哪一个呢？

因此，我们需要从右下角开始反过来寻找一条需要最小血量的路径。

首先，骑士的生命值不能为 0，因此最小的生命初始值应该为 1.

然后，骑士需要从右边或者下面选择一个需要生命值最小的路径

定义hp[i][j]从当前格子走到右下角的最小需要的生命值， dungeon[i][j]为当前格子的扣血量

$$
need = min(hp[i +1][j], hp[i][j+1])-dungeon[i][j] \
hp[i][j]=
\begin{cases}
1, need \leq 0\
need, need > 0\
\end{cases}
$$

如果需要的血量小于 0，就说明当前格子存在加血，因此只需要最低生命值（1）就可以通关。

因为使用右下角开始的，因此右下角为最小子问题，就等于

$$
need = 1-dungeon[i][j] \
hp[row][col]=
\begin{cases}
1, need \leq 0\
need, need > 0\
\end{cases}
$$

我们来看题目的例子

-2 (K) -3 3
-5 -10 1
10 30 -5 (P)

生成的hp为

7 5 2
6 11 5
1 1 6

因此，hp[0][0]显然就是从左上角走到右下角需要的最小的血量。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int row = dungeon.size();
        int col = dungeon[0].size();
        vector<vector<int> > hp(row + 1, vector<int>(col + 1, INT_MAX));
        hp[row - 1][col] = 1;
        hp[row][col - 1] = 1;
        for (int i = row - 1; i >= 0; i--) {
          for (int j = col - 1; j >= 0; j--) {
              int need = min(hp[i + 1][j], hp[i][j + 1]) - dungeon[i][j];
              hp[i][j] = need <= 0 ? 1 : need;
          }
        }
        return hp[0][0];
    }
};

这个算法使用动态规划的思想，填充了一个 n*m 的数组，因此时间复杂度为O(nm)，空间复杂度为O(nm)

Summary

这是还是一道传统的动态规划问题，虽然难度还是hard，但是代码逻辑上却很简洁。

土豪通道
0%