Dungeon Game
Solve this ProblemTest Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ dungeon.length, dungeon[0].length ≤ 15 - ◆
-1000 ≤ dungeon[i][j] ≤ 1000
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Recursive Without Memoization
BruteThe running total must stay at least 1 at every cell it passes through, so work out the minimum value needed entering each cell to keep it that way all the way to the bottom-right corner. At the bottom-right cell itself, the minimum entering value is whatever keeps the total at least 1 after this cell's own effect, which is max(1, 1 - cell's value). At any other cell, the path continues to whichever of the two next cells — one step down or one step right — needs less entering value to survive from there, so the value needed entering the current cell is that smaller requirement minus this cell's own effect, floored at 1 (since the running total can never be recorded as 0 or negative). Stepping past the bottom or right edge simply isn't a valid move. Recursing from the top-left corner finds the minimum starting value, though the same cell ends up recomputed every time a different path reaches it.
O(2^(m+n))O(m + n)1class Solution {
2 private int[][] dungeon;
3 private int m;
4 private int n;
5
6 public int calculateMinimumHP(int[][] dungeon) {
7 this.dungeon = dungeon;
8 this.m = dungeon.length;
9 this.n = dungeon[0].length;
10 return solve(0, 0);
11 }
12
13 private int solve(int i, int j) {
14 if (i == m - 1 && j == n - 1) {
15 return Math.max(1, 1 - dungeon[i][j]);
16 }
17 int down = (i + 1 < m) ? solve(i + 1, j) : Integer.MAX_VALUE;
18 int right = (j + 1 < n) ? solve(i, j + 1) : Integer.MAX_VALUE;
19 int need = Math.min(down, right) - dungeon[i][j];
20 return Math.max(1, need);
21 }
22}Optimal — Bottom-Up 1D DP
OptimalWork backward from the bottom-right corner. Track, for the row currently being processed, the minimum value needed entering each column to keep the running total at least 1 all the way to the end. Two sentinel facts kick off the sweep: finishing at the bottom-right cell needs no further cushion beyond surviving that cell itself, and there's no valid move past the last column. Then, moving from the bottom row upward and from the last column backward within each row, every cell's requirement is the smaller of the two requirements below/to the right of it, minus this cell's own effect, floored at 1 so a positive-value cell never produces a requirement below 1. Once every row has been swept through this way, the first column of the top row holds the minimum starting value for the whole grid.
O(m × n)O(n)1class Solution {
2 public int calculateMinimumHP(int[][] dungeon) {
3 int m = dungeon.length, n = dungeon[0].length;
4 int[] dp = new int[n + 1];
5 Arrays.fill(dp, Integer.MAX_VALUE);
6 dp[n - 1] = 1;
7 for (int i = m - 1; i >= 0; i--) {
8 dp[n] = (i == m - 1) ? 1 : Integer.MAX_VALUE;
9 for (int j = n - 1; j >= 0; j--) {
10 int need = Math.min(dp[j], dp[j + 1]) - dungeon[i][j];
11 dp[j] = Math.max(1, need);
12 }
13 }
14 return dp[0];
15 }
16}