Dungeon Game

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& g) {
        int m = g.size(), n = g[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 r = m - 1; r >= 0; --r) {
            for (int c = n - 1; c >= 0; --c) {
                int need = min(dp[r + 1][c], dp[r][c + 1]) - g[r][c];
                dp[r][c] = max(1, need);
            }
        }
        return dp[0][0];
    }
};

import "math"

func calculateMinimumHP(g [][]int) int {
    m, n := len(g), len(g[0])
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
        for j := range dp[i] {
            dp[i][j] = math.MaxInt32
        }
    }
    dp[m][n-1] = 1
    dp[m-1][n] = 1
    for r := m - 1; r >= 0; r-- {
        for c := n - 1; c >= 0; c-- {
            nxt := dp[r+1][c]
            if dp[r][c+1] < nxt {
                nxt = dp[r][c+1]
            }
            need := nxt - g[r][c]
            if need < 1 {
                need = 1
            }
            dp[r][c] = need
        }
    }
    return dp[0][0]
}

from typing import List

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        m, n = len(dungeon), len(dungeon[0])
        INF = float('inf')
        dp = [[INF] * (n + 1) for _ in range(m + 1)]
        dp[m][n - 1] = 1
        dp[m - 1][n] = 1
        for r in range(m - 1, -1, -1):
            for c in range(n - 1, -1, -1):
                need = min(dp[r + 1][c], dp[r][c + 1]) - dungeon[r][c]
                dp[r][c] = max(1, need)
        return dp[0][0]

var calculateMinimumHP = function(dungeon) {
    const m = dungeon.length, n = dungeon[0].length;
    const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(Infinity));
    dp[m][n - 1] = 1;
    dp[m - 1][n] = 1;
    for (let r = m - 1; r >= 0; r--) {
        for (let c = n - 1; c >= 0; c--) {
            const need = Math.min(dp[r + 1][c], dp[r][c + 1]) - dungeon[r][c];
            dp[r][c] = 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[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);
        dp[m][n - 1] = 1;
        dp[m - 1][n] = 1;
        for (int r = m - 1; r >= 0; r--) {
            for (int c = n - 1; c >= 0; c--) {
                int need = Math.min(dp[r + 1][c], dp[r][c + 1]) - dungeon[r][c];
                dp[r][c] = Math.max(1, need);
            }
        }
        return dp[0][0];
    }
}

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