174. Dungeon Game!

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        // bottom up
        // set M[i][j] as the health of the knight at position dungeon[i][j]
        // whether the knight is able to reach the target position depends
        // on the cell values on the right or down side of [i][j]
        // M[i][j] = Math.max(1, Math.min(M[i+1][j], M[i][j+1])-dungeon[i][j]);
        int m = dungeon.length;
        int n = dungeon[0].length;
        int[] memo = new int[n];
        
        for (int i=m-1; i>=0; i--){
            for (int j = n-1; j>=0; j--){
                if(j==n-1 && i ==m-1){
                    memo[j]=Math.max(1, 1-dungeon[i][j]);
                }else if (j==n-1){
                    memo[j]=Math.max(1, memo[j]-dungeon[i][j]);
                }else if (i==m-1){
                    memo[j]=Math.max(1, memo[j+1]-dungeon[i][j]);
                }else {
                    memo[j] = Math.max(1, Math.min(memo[j], memo[j+1])-dungeon[i][j]);
                }
            }
        }
        
        return memo[0];
    }
}