[LeetCode] 174. Dungeon Game

Posted on | In

Problem

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.

Explanation

  1. We can use dynamic programming to solve this problem.

  2. Dynamic state is a two dimensional array. dp[r][c] means the initial health point before fighting at position (r, c), so the return result will be dp[0][0].

  3. Dynamic init, we create one more row and column, and we assign these whole new row and new column’s elements all be maximum number. We will start from the princess’s position, and the princess’s position depends on its down and right position. We will assign these two positions be 1 instead of maximum because after fighting at the pricness’s position, the knight at least have 1 health point before going to down or right position.

  4. Dynamic function, the health point before fighting is dp[r][c], so before fighting at its down position, the health point for dp[r+1][c] = dp[r][c] + dungeon[r][c], in other word, dp[r][c] is depend on its down position, so dp[r][c] = dp[r+1][c] - dungeon[r][c]. If the knight goes to the right position, then dp[r][c] = dp[r][c+1] - dungeon[r][c]. To use less point as possible, the knight will choose the less point to go to, so it is min[dp[r+1][c], dp[r][c+1]. If the subtraction result is negative, then we will lose, so dp[r][c] has at least 1 health point. Therefore, we get our dynamic function dp[r][c] = Math.max(1, Math.min(dp[r+1][c], dp[r][c+1]) - dungeon[r][c]).

  5. Dynamic result is dp[0][0] which is the beginning top left position.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int row = dungeon.length + 1;
        int col = dungeon[0].length + 1;
        int[][] dp = new int[row][col];

        for (int i = 0; i < dp.length; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[row-1][col-2] = 1;
        dp[row-2][col-1] = 1;

        for (int r = row - 2; r >= 0; r--) {
            for (int c = col - 2; c >= 0; c--) {
                dp[r][c] = Math.max(1, Math.min(dp[r+1][c], dp[r][c+1]) - dungeon[r][c]);
            }
        }

        return dp[0][0];
    }
}