174_DungeonGame

// C++:
// -----
int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int r = dungeon.size();
        int c = dungeon[0].size();
        vector<vector<int>> sol(r, vector<int>(c));
        
        sol[r-1][c-1] = dungeon[r-1][c-1] > 0 ? 1 : 1-dungeon[r-1][c-1];
        
        for(int i = r-2; i >= 0; --i)
            sol[i][c-1] = max(sol[i+1][c-1] - dungeon[i][c-1], 1);
        for(int j = c-2; j >= 0; --j)
            sol[r-1][j] = max(sol[r-1][j+1] - dungeon[r-1][j], 1);
        
        for(int i = r-2; i >= 0; --i){
            for(int j = c-2; j >= 0; --j){
                sol[i][j] = max(min(sol[i+1][j], sol[i][j+1])-dungeon[i][j], 1);
            }
        }
        return sol[0][0];
    }
    
// Java:
// -----
public int calculateMinimumHP(int[][] dungeon) {
        int r = dungeon.length;
        int c = dungeon[0].length;
        int[][] sol = new int[r][c];
        
        sol[r-1][c-1] = dungeon[r-1][c-1] > 0 ? 1 : 1-dungeon[r-1][c-1];
        
        for(int i = r-2; i >= 0; --i)
            sol[i][c-1] = Math.max(sol[i+1][c-1] - dungeon[i][c-1], 1);
        for(int j = c-2; j >= 0; --j)
            sol[r-1][j] = Math.max(sol[r-1][j+1] - dungeon[r-1][j], 1);
        
        for(int i = r-2; i >= 0; --i){
            for(int j = c-2; j >= 0; --j){
                sol[i][j] = Math.max(Math.min(sol[i+1][j], sol[i][j+1])-dungeon[i][j], 1);
            }
        }
        return sol[0][0];
    }

# Python3:
# --------
def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        r = len(dungeon)
        c = len(dungeon[0])
        sol = [[0]*c for i in range(r)]
        
        sol[r-1][c-1] = 1 if dungeon[r-1][c-1] > 0 else 1-dungeon[r-1][c-1]
        
        for i in range(r-2, -1, -1):
            sol[i][c-1] = max(sol[i+1][c-1] - dungeon[i][c-1], 1)
        for j in range(c-2, -1, -1):
            sol[r-1][j] = max(sol[r-1][j+1] - dungeon[r-1][j], 1)
        
        for i in range(r-2, -1, -1):
            for j in range(c-2, -1, -1):
                sol[i][j] = max(min(sol[i+1][j], sol[i][j+1])-dungeon[i][j], 1)
            
        return sol[0][0]