174. Dungeon Game

At a Glance

• Topic: dp-2d
• Pattern: Dynamic Programming — reverse reachability / min initial resource
• Difficulty: Hard
• Companies: Google, Amazon, Microsoft, Uber, Bloomberg
• Frequency: Medium
• LeetCode: 174

Problem (one-liner)

Grid of rooms with gains/losses (dungeon[row][col]). Start top-left, move only right or down; minimum HP must stay strictly positive at every step. Return the minimum initial HP to reach bottom-right alive.

Recognition Cues

• Minimum starting resource so path never drops below 1
• Future depends on later rooms — reverse DP from goal (like “min cost from here to exit”)
• Unlike max-sum path: need minimax survival, not max loot

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute all paths — exponential.
• Reverse DP — need[row][col] = minimum HP entering (row,col) to reach princess — O(mn) time, O(n) space possible — optimal.

Optimal Solution

Go

func calculateMinimumHP(dungeon [][]int) int {
	rowCount := len(dungeon)
	colCount := len(dungeon[0])
	// need[row][col] = min HP when ENTERING this cell to survive to princess
	need := make([][]int, rowCount)
	for row := range need {
		need[row] = make([]int, colCount)
	}
	for row := rowCount - 1; row >= 0; row-- {
		for col := colCount - 1; col >= 0; col-- {
			if row == rowCount-1 && col == colCount-1 {
				need[row][col] = max(1, 1-dungeon[row][col])
				continue
			}
			var bestNext int
			if row == rowCount-1 {
				bestNext = need[row][col+1]
			} else if col == colCount-1 {
				bestNext = need[row+1][col]
			} else {
				bestNext = min(need[row+1][col], need[row][col+1])
			}
			need[row][col] = max(1, bestNext-dungeon[row][col])
		}
	}
	return need[0][0]
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

JavaScript

function calculateMinimumHP(dungeon) {
  const rowCount = dungeon.length;
  const colCount = dungeon[0].length;
  const need = Array.from({ length: rowCount }, () =>
    new Array(colCount).fill(0)
  );
  for (let row = rowCount - 1; row >= 0; row -= 1) {
    for (let col = colCount - 1; col >= 0; col -= 1) {
      if (row === rowCount - 1 && col === colCount - 1) {
        need[row][col] = Math.max(1, 1 - dungeon[row][col]);
        continue;
      }
      let bestNext;
      if (row === rowCount - 1) {
        bestNext = need[row][col + 1];
      } else if (col === colCount - 1) {
        bestNext = need[row + 1][col];
      } else {
        bestNext = Math.min(need[row + 1][col], need[row][col + 1]);
      }
      need[row][col] = Math.max(1, bestNext - dungeon[row][col]);
    }
  }
  return need[0][0];
}

Walkthrough

Bottom-right needs enough HP after accounting for final cell. Walk backward: before entering a cell, you must cover loss dungeon[row][col] and still have enough for the cheaper optimal next step.

Invariant: need[row][col] is the minimum HP at entry to (row,col) to eventually reach the princess with HP always ≥ 1.

Edge Cases

• Single cell — max(1, 1 - dungeon[0][0])
• All positive rooms — still at least 1 HP everywhere
• Heavy negatives on every step — answer grows

Pitfalls

• Forward DP on max gain — wrong objective (survival vs sum)
• Off-by-one on “strictly positive” — clamp with max(1, ...)

Similar Problems

• 62. Unique Paths — grid path counting (Medium)
• 329. Longest Increasing Path in a Matrix — grid DP + graph (Hard)
• 312. Burst Balloons — coupled intervals / tricky recurrence (Hard)

Variants

• Four directions allowed — need SPFA or Dijkstra-style on states (row,col,hp) or BFS levels
• Maximize loot with survival — lexicographic or constrained optimization
• Multiple princesses / exits — min over targets in reverse multi-target DP

Mind-Map Tags

#grid-dp #reverse-dp #min-initial-resource #survival #clamp-positive