174. Dungeon Game

Time: O(m x n)

Space: O(m x n)

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?