Dungeon Game

hard array dp matrix

Problem

A knight starts at the top-left of a dungeon grid and must reach the princess at the bottom-right, moving only right or down. Each cell adds its value (negative for damage, positive for healing) to the knight's HP, which must stay ≥ 1 at all times. Return the minimum starting HP that guarantees a safe path.

Inputdungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]

Output7

Going forward you don't know future demons. Solve backwards: at each cell compute the minimum HP needed to enter so that, after the cell's effect, you still have at least the required HP of the better neighbor.

dungeon rows (semicolons between rows; commas inside)

def calculate_minimum_hp(dungeon):
    m, n = len(dungeon), len(dungeon[0])
    INF = float('inf')
    dp = [[INF] * (n + 1) for _ in range(m + 1)]
    dp[m][n - 1] = dp[m - 1][n] = 1
    for i in range(m - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            need = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]
            dp[i][j] = max(1, need)
    return dp[0][0]

function calculateMinimumHP(dungeon) {
  const m = dungeon.length, n = dungeon[0].length;
  const INF = Infinity;
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(INF));
  dp[m][n - 1] = dp[m - 1][n] = 1;
  for (let i = m - 1; i >= 0; i--) {
    for (let j = n - 1; j >= 0; j--) {
      const need = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
      dp[i][j] = Math.max(1, need);
    }
  }
  return dp[0][0];
}

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length, n = dungeon[0].length;
        int[][] dp = new int[m + 1][n + 1];
        for (int[] r : dp) Arrays.fill(r, Integer.MAX_VALUE);
        dp[m][n - 1] = dp[m - 1][n] = 1;
        for (int i = m - 1; i >= 0; i--)
            for (int j = n - 1; j >= 0; j--) {
                int need = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                dp[i][j] = Math.max(1, need);
            }
        return dp[0][0];
    }
}

int calculateMinimumHP(vector<vector<int>>& dungeon) {
    int m = dungeon.size(), n = dungeon[0].size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
    dp[m][n - 1] = dp[m - 1][n] = 1;
    for (int i = m - 1; i >= 0; i--)
        for (int j = n - 1; j >= 0; j--) {
            int need = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
            dp[i][j] = max(1, need);
        }
    return dp[0][0];
}

Explanation

The twist in this grid problem is that going forward you cannot tell how much damage lies ahead, so a greedy left-to-right pass fails. The fix is to solve it backwards, from the princess's cell toward the start.

We define dp[i][j] as the minimum HP you must have entering cell (i,j) to survive the rest of the journey. After applying the cell's value you must still have at least the requirement of the better next cell, so need = min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j].

Health must never drop below 1, so we clamp with dp[i][j] = max(1, need). We seed the two sentinels just past the princess to 1 so the bottom-right corner is computed correctly, and the answer is dp[0][0].

Example: [[-2,-3,3],[-5,-10,1],[10,30,-5]] gives 7. Even though some cells heal a lot, the early damage means you must start with 7 HP so you never dip to 0 along the safest path.

We compute every cell once in reverse order, doing constant work each, so it runs in m · n time.

Time: O(m·n) Space: O(m·n)