174. Dungeon Game

HardView on LeetCode

Array Dynamic Programming Matrix

Time: O(m x n)

Space: O(m x n)

Problem Overview

Forward DP fails because we don't know how much health we'll have in the future.

Intuition

Forward DP fails because we don't know how much health we'll have in the future. Bottom-up DP from the bottom-right: dp[i][j] = minimum health needed when entering cell (i,j) to survive the rest of the journey. dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]).

Algorithm

1dp[i][j] = minimum health needed at (i,j).
2Base: dp[m-1][n-1] = max(1, 1 - dungeon[m-1][n-1]).
3Last row/col: only one direction available.
4Fill backwards: dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]).
5Answer is dp[0][0].

Example Walkthrough

Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]

1.dp[2][2]=max(1,1+5)=6. dp[2][1]=max(1,6-30)=1. dp[2][0]=max(1,1-10)=1.
2.dp[1][2]=max(1,6-1)=5. dp[1][1]=max(1,min(1,5)+10)=11. dp[1][0]=max(1,min(11,1)+5)=6.
3.dp[0][2]=max(1,5-3)=2. dp[0][1]=max(1,min(2,11)+3)=5. dp[0][0]=max(1,min(5,6)+2)=7.

Output: 7

Common Pitfalls

•Ensure dp values are at least 1 - you cannot enter a cell with 0 or negative health.

174.cs

// Approach: Reverse DP from the bottom-right princess cell back to the top-left starting cell.
// dp[i][j] = minimum health the knight needs when entering cell (i,j) to survive to the end.
// From cell (i,j): the knight can go right or down, so dp[i][j] = min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j].
// Clamp dp[i][j] to at least 1 (the knight must always have at least 1 HP).
// Forward DP does not work here because minimum health depends on future choices, not past ones.
// Time: O(m x n) Space: O(m x n); reducible to O(n) with a rolling row.

public class Solution
{
    public int CalculateMinimumHP(int[][] dungeon)
    {
        int m = dungeon.Length;
        int n = dungeon[0].Length;
        int[,] dp = new int[m + 1, n + 1];

        for (int i = 0; i <= m; i++)
        {
            for (int j = 0; j <= n; j++)
                dp[i, j] = int.MaxValue;
        }

        dp[m, n - 1] = 1;
        dp[m - 1, n] = 1;

        for (int i = m - 1; i >= 0; i--)
        {
            for (int j = n - 1; j >= 0; j--)
            {
                dp[i, j] = Math.Min(dp[i + 1, j], dp[i, j + 1]) - dungeon[i][j];
                dp[i, j] = Math.Max(dp[i, j], 1);
            }
        }

        return dp[0, 0];
    }
}

Was this solution helpful?