DungeonGame

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
         if(dungeon == null || dungeon.length == 0 || dungeon[0].length == 0){
            return 0;
        }
        
        int m = dungeon.length;
        int n = dungeon[0].length;
        int[][] M = new int[m][n];

        for(int i = m - 1; i >= 0; i--){
            for(int j = n - 1; j >= 0; j--){
                if(i == m - 1 && j == n - 1){
                    M[m - 1][n - 1] = Math.max(1, 1 - dungeon[m - 1][n - 1]); 
                }else if(i == m - 1){
                    M[m - 1][j] = Math.max(M[m - 1][j + 1] - dungeon[m - 1][j], 1);
                }else if(j == n - 1){
                    M[i][n - 1] = Math.max(M[i + 1][n - 1] - dungeon[i][n - 1], 1);
                }else{
                    M[i][j] = Math.min(Math.max(M[i + 1][j] - dungeon[i][j], 1), Math.max(M[i][j + 1] - dungeon[i][j], 1));
                }
            }
        }
        return M[0][0];
    }
}