DSA problem
Dungeon Game
A knight starts at the top-left of an m x n dungeon and wants to reach the princess at the bottom-right. The dungeon's cells contain integers: negative values are damage (monsters), positive values are healing (potions), and zero is empty. The knight's health must stay strictly positive at all times — if it drops to 0 or below at any cell (including the start and the end), the knight dies. He moves only right or down. Return the minimum initial health he needs to guarantee a safe arrival.
A common wrong approach is a top-down DP that maximizes the running sum: pick the path that loses the least, then return 1 - min_prefix. This fails because choosing the path with the highest minimum prefix is not the same as choosing the path that requires the smallest starting health — the same sum can arrive via different trajectories, and what matters is the worst dip.
The clean technique is bottom-up DP starting from the destination. Let dp[i][j] = the minimum health the knight needs upon entering cell (i, j) to survive from there to the end. At the destination he must end with at least 1 health, so dp[m - 1][n - 1] = max(1, 1 - dungeon[m - 1][n - 1]). For any other cell, after stepping in he'll then move to (i + 1, j) or (i, j + 1) — whichever needs less. So he must enter with enough health that after applying dungeon[i][j] he still has at least min(dp[i + 1][j], dp[i][j + 1]). That gives dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]).
The max(1, ...) clamp enforces the rule that health must stay positive. Compress to a single 1-D array of length n since the recurrence only reads "below" and "right." Total: O(m * n) time and O(n) space. The answer is dp[0][0].
Examples
dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]7dungeon = [[0]]1dungeon = [[100]]1Constraints
- m == dungeon.length
- n == dungeon[i].length
- 1 <= m, n <= 200
- -1000 <= dungeon[i][j] <= 1000
- The knight's health must remain >= 1 in every visited cell, including the start and the destination.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.