刷完第64题的时候，推荐了一道关联题目#174 Dungeon Game，我一开始以为和64一样，但是后来就发现太不一样了。看完解析还是有点懵懵懂懂，因此留个笔记整理自己的思路。

Question

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)

Notes:

  • 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

第一眼看上去，这个问题就如同是”Maximum/Minimum Path Sum”的亲戚题目。

但是一条路径得出的总和最大值并不能得出准确的最小生命值，因为这道题要保证在走过每一个格子的时候，血量不能低于0，不然判 Knight 死亡。

比如说，这里有两条不同的路径： 0 -> -300 -> 310 -> 0 和 0 -> -1 -> 2 -> 0。

两条路径，最后相加的总和分别是 -300 + 310 = 10 和 -1 + 2 = 1 。

显然第一条路获得的血量（数值）比第二个高（大），但是为了不让我们的 Knight 死，第一条路径要求的初始血量至少是301。

然而第二条路径初始血量仅为至少2。

幸运的是，这个问题可以用和 grid walking 很像的 table-filling 的DP方法来解决。

解题思路如下

一开始，我们应该创建一个和 Dungeon 同样大小的二维数组 Health 。

其中，Health[i][j] 代表的是该格最小的血量以保证 Knight 在进入 Room(i,j) 之后血量不会低于0.

显然，Health[0][0] 就是我们要的最终答案——最小初始血量。

因此，这道题我们要倒着做，从 Princess （右下角）到 Knight （左上角）来计算和维护我们的二维数组 Health 。

然后，我们就开始计算离开 Room(i,j) 时所需要的最小血量。

离开的时候，我们有且仅有两条路可以走： Room(i+1,j) 和 Room(i,j+1) 。

当然，我们会选择使 Health 值最小的房间，也就是说 Knight 完成任务所需要的最小血量。

这样，我们就会有 min_HP_on_exit = min(Health[i+1][j], Health[i][j+1])

现在， Health[i][j] 就可以从 Dungeon[i][j] 中计算出来。

min_HP_on_exit 将会基于以下集中情况：

  1. Dungeon[i][j] == 0

    什么事情都不会发生，骑士将会安然无恙的从该房间离开。

    离开时的血量将和他进来时的血量一直，即： Health[i][j] = min_HP_on_exit

  2. Dungeon[i][j] < 0

    为了使 Knight 的血量不低于0，在进入 Room(i,j) 之前，其血量必需大于 min_HP_on_exit 。

    那么，最少需要有 -Dungeon[i][j] 的补偿量，所以我们会有 Health[i][j] = min_HP_on_exit - Dungeon[i][j] 。

  3. Dungeon[i][j] > 0

    骑士可以最小以 min_HP_on_exit - Dungeon[i][j] 的血量进入 Room[i][j] 。

    但是，这个 min_HP_on_exit - Dungeon[i][j] 的数值可以小于等于0。

    那么，在这种情况下，我们必须拿1和这个数值比以确保我们 Health[i][j] 是正数：

    Health[i][j] = max(min_HP_on_exit - Dungeon[i][j], 1)

注意到 Dungeon[i][j] > 0 其实还覆盖着其他的两种情况，但是对于任何Dungeon[i][j]我们都可以用同一个等式来计算：

1
Health[i][j] = max(min_HP_on_exit - Dungeon[i][j], 1)

到了最后， Health[0][0]就是我们最终的答案。

与此同时，像许多其他table-filling类型的问题，二维数组也可以被滚动数组所替代。

Also, like many other “table-filling” problems, the 2D array D can be replaced with a 1D “rolling” array here.

Solution

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
public class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
    	int m = dungeon.length;
    	int n = dungeon[0].length;
     
    	//init dp table
    	int[][] h = new int[m][n];
     
    	h[m - 1][n - 1] = Math.max(1 - dungeon[m - 1][n - 1], 1);
     
    	//init last row
    	for (int i = m - 2; i >= 0; i--) {
    		h[i][n - 1] = Math.max(h[i + 1][n - 1] - dungeon[i][n - 1], 1);
    	}
     
    	//init last column
    	for (int j = n - 2; j >= 0; j--) {
    		h[m - 1][j] = Math.max(h[m - 1][j + 1] - dungeon[m - 1][j], 1);
    	}
     
    	//calculate dp table
    	for (int i = m - 2; i >= 0; i--) {
    		for (int j = n - 2; j >= 0; j--) {
    			int down = Math.max(h[i + 1][j] - dungeon[i][j], 1);
    			int right = Math.max(h[i][j + 1] - dungeon[i][j], 1);
    			h[i][j] = Math.min(right, down);
    		}
    	}
     
    	return h[0][0];
    }
}

Reference

Solution - LeetCode

LeetCode : Dungeon Game #174 - Github