Dungeon Game

Share

A knight starts in top-left of a dungeon, must reach bottom-right to save the princess. Each cell adds or subtracts health. Find minimum initial health (at least 1) needed.

Example 1
Input: [[-2,-3,3],[-5,-10,1],[10,30,-5]] → Output: 7
Example 2
Input: [[0]] → Output: 1

Solution Approach

Work backwards from bottom-right. dp[i][j] = minimum health needed when entering cell (i,j). dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]).

  • dp[m][n-1] = max(1, 1 - dungeon[m-1][n-1]).
  • For i from m-1 to 0, j from n-1 to 0 (excluding bottom-right):
  • need = min(right_need, down_need) - dungeon[i][j].
  • dp[i][j] = max(1, need).
Java
class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length, n = dungeon[0].length;
        int[][] dp = new int[m + 1][n + 1];
        for (int[] row : dp) java.util.Arrays.fill(row, Integer.MAX_VALUE);
        dp[m][n-1] = dp[m-1][n] = 1;
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int need = Math.min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j];
                dp[i][j] = Math.max(1, need);
            }
        }
        return dp[0][0];
    }
}
  • Time Complexity: O(M*N)
  • Space Complexity: O(M*N)