[leetcode #174] Dungeon Game

Problem

The demons had captured the princess 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 was initially positioned in the top-left room and must fight his way through 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 (represented by negative integers), so the knight loses health upon entering these rooms; other rooms are either empty (represented as 0) or contain magic orbs that increase the knight's health (represented by positive integers).

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

Return the knight's minimum initial health so that he can rescue the princess.

Note that 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.

Example 1:

Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Output: 7
Explanation: The initial health of the knight must be at least 7 if he follows the optimal path: RIGHT-> RIGHT -> DOWN -> DOWN.

Example 2:

Input: dungeon = [[0]]
Output: 1

Constraints:

・ m == dungeon.length
・ n == dungeon[i].length
・ 1 <= m, n <= 200
・ -1000 <= dungeon[i][j] <= 1000

Idea

시작점부터 시작해서 풀려고 온갖 애를 썼는데 결국 풀지 못 했다. Solution을 보고 나니 전형적인 backtracking 문제라는 걸 알 수 있었다. Backtracking을 위해 주어진 array (=dungeon)과 똑같은 크기의 array를 만들고, 도착점까지 도달할 때까지 필요한 최소한의 체력을 저장한다.

공주가 있는 지점은 dungeon의 값 그대로의 체력이 필요하다. 제일 아래 줄에서는 dungeon의 값에서 오른쪽에 인접한 값을 뺀 만큼의 체력이 필요하다. 제일 오른쪽 줄에서는 dungeon의 값에서 위쪽에 인접한 값을 뺀 만큼의 체력이 필요하다. 그 외의 경우에는 오른쪽과 왼쪽의 값을 비교하여 더 작은 값을 dungeon에서 뺀 값만큼의 체력이 필요하다.

이렇게 계산한 값이 0보다 클 경우 체력이 필요하지 않으므로 0을 저장하고 0보다 작을 경우 -1을 곱해 필요한 체력을 저장한다.

Backtracking을 끝낸 뒤 시작점에 도달하면 필요한 체력에 1을 더해 답을 return하면 된다. 1을 더하는 이유는 기사의 체력이 0이 되면 안 되기 때문이다.

Solution

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;
        int[][] dp = new int[m][n];

        for (int i=m-1; i >= 0; i--) {
            for (int j=n-1; j >= 0; j--) {
                if (i == m-1 && j == n-1)
                    dp[i][j] = dungeon[i][j];
                else if (i != m-1 && j != n-1)
                    dp[i][j] = dungeon[i][j] - Math.min(dp[i+1][j], dp[i][j+1]);
                else
                    dp[i][j] = dungeon[i][j] - (i == m-1 ? dp[i][j+1] : dp[i+1][j]);
                dp[i][j] = dp[i][j] > 0 ? 0 : -dp[i][j];
            }
        }

        return dp[0][0] + 1;
    }
}

Reference

https://leetcode.com/problems/dungeon-game/