Dungeon Game
Understanding the Problem
We need to find the minimum starting health for the knight so that he can travel from the top-left corner to the bottom-right corner, moving only right or down, and never have his health drop to 0 or below at any point along the path.
This differs from a standard minimum-path-sum problem. With path sum, only the total matters. Here, every intermediate state matters: the knight must survive at every step, not merely arrive at the end with positive health. A path that passes through a large health boost late in the journey is useless if the knight dies before reaching it.
The minimum health needed at any cell depends on what lies ahead rather than on what came before. If the path after a cell is damaging, the knight needs more health when entering it. If the path ahead is full of power-ups, he can enter with less. Because the requirement at each cell is determined by the future, the problem is solved by working backwards from the princess's cell.
Key Constraints:
1 <= m, n <= 200→ The grid can have up to 40,000 cells, so an O(m*n) dynamic programming solution runs comfortably. Enumerating all paths is exponential and rules out brute force for large grids.-1000 <= dungeon[i][j] <= 1000→ A path visits at most m + n - 1 = 399 cells, so any running sum stays within roughly ±400,000. 32-bit integers are enough.
Approach 1: Brute Force (DFS with All Paths)
Intuition
Enumerate every possible path from the top-left to the bottom-right. For each path, calculate the minimum starting health needed so the knight survives every room, then return the minimum across all paths.
For a single path, the minimum starting health is determined by the worst dip in the running sum of room values. If we start with health h and the running sum at some point reaches its lowest value minPrefix, then survival requires h + minPrefix >= 1, so h >= 1 - minPrefix.
Algorithm
- Use DFS to explore all paths from (0, 0) to (m-1, n-1), moving only right or down.
- At each cell, add the cell's value to the running sum. Track the minimum prefix sum seen so far along this path.
- When we reach (m-1, n-1), compute the starting health needed for this path:
max(1, 1 - minPrefixSum). - Return the minimum starting health across all paths.
Example Walkthrough
Code
- Time Complexity: O(C(m+n-2, m-1)). The number of paths from top-left to bottom-right is "m+n-2 choose m-1," which grows combinatorially. For a 200x200 grid, this is far beyond what can be enumerated.
- Space Complexity: O(m + n). The recursion depth equals the path length, which is m + n - 2.
The DFS recomputes health requirements for the same suffixes across many overlapping paths. The next approach computes the minimum health needed at each cell exactly once and reuses it.
Approach 2: Reverse DP (2D Table)
Intuition
A forward DP, where dp[i][j] is computed from dp[i-1][j] and dp[i][j-1], works for Minimum Path Sum but breaks down here. At each cell, two quantities matter: the running sum so far (to know current health) and the minimum dip along the way (to know the starting health needed). These two quantities are at odds. A path with a better running sum might have had a worse dip earlier, and a path with a smaller dip might have a worse sum going forward. Neither value alone tells you which incoming path to keep, so the forward state cannot be reduced to a single number per cell.
Reversing direction fixes this. Process cells from bottom-right to top-left and define dp[i][j] as the minimum health the knight needs when entering cell (i, j) to survive the rest of the journey. This is a single well-defined number per cell because everything it depends on, the path ahead, has already been computed.
The recurrence is dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]). When the knight enters cell (i, j), his health changes by dungeon[i][j]. After that change, he needs at least min(dp[i+1][j], dp[i][j+1]) health, since he is free to pick whichever next cell demands less. The max(1, ...) clamp handles rooms with large heals: even if the orb in this room more than covers the future requirement, the knight must still be alive when he walks in, so the requirement when entering any cell never drops below 1.
Algorithm
- Create a 2D DP table where
dp[i][j]= minimum health needed when entering cell (i, j). - Base case: At (m-1, n-1), the knight needs
max(1, 1 - dungeon[m-1][n-1])health. - Last row and last column: Only one direction is available (right in the last row, down in the last column), so fill these directly from the single neighbor.
- General case: For cell (i, j), the knight will choose the direction that requires less health. So
dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]). - Return
dp[0][0].
Example Walkthrough
Code
- Time Complexity: O(m * n). We fill each cell of the DP table exactly once, with O(1) work per cell.
- Space Complexity: O(m * n). The DP table is the same size as the input grid.
The time complexity is already optimal, but the table uses O(m * n) extra space. Each row of the DP table depends only on the row below it, so a single 1D array is enough.
Approach 3: Space-Optimized DP
Intuition
Looking at the recurrence, cell (i, j) depends only on (i+1, j) and (i, j+1). This means we only need the current row and the row below. We can go a step further and use a single 1D array. Process columns from right to left within each row. When we compute dp[j], the value dp[j] currently holds is from row i+1 (not yet overwritten), and dp[j+1] is from row i (already updated for the current row). So both dependencies are available.
Algorithm
- Create a 1D array
dpof size n. - Process rows from bottom (m-1) to top (0). Within each row, process columns from right (n-1) to left (0).
- For the bottom-right cell:
dp[n-1] = max(1, 1 - dungeon[m-1][n-1]). - For other cells in the last row:
dp[j] = max(1, dp[j+1] - dungeon[m-1][j]). - For other rows: at each cell (i, j), pick
min(dp[j], dp[j+1])and computedp[j] = max(1, min - dungeon[i][j]). - Return
dp[0].
Example Walkthrough
Code
- Time Complexity: O(m * n). Same as Approach 2. We process each cell exactly once.
- Space Complexity: O(n). We use a single 1D array of size n instead of an m x n table.