Simple 4ms java solution using DP


  • 2
    C
    public class Solution {
        public int calculateMinimumHP(int[][] dungeon) {
            int n = dungeon.length;
            if (n <= 0) return 1;
            int m = dungeon[0].length;
            int[][] life = new int[n][m];
            for (int i = n-1;i >= 0; --i) {
                for (int j = m-1; j >= 0; --j) {
                    int futureMin = 1;
                    if (i < n-1) {
                        futureMin = life[i+1][j];
                        if (j < m-1) futureMin = Math.min(futureMin, life[i][j+1]);
                    }
                    else if (j < m-1) futureMin = life[i][j+1];
                    life[i][j] = Math.max(1, futureMin - dungeon[i][j]); 
                    // System.out.println("" + i + "," + j + "=" + life[i][j]);
                }
            }
            return life[0][0];
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.