Share My Java DP Solution


  • 0
    M
        public int calculateMinimumHP(int[][] dungeon) {
            if (dungeon == null || dungeon.length == 0) return 0;
            int m = dungeon.length, n = dungeon[0].length;
            int[][] hp = new int[m][n];
            int h = 1;
            for (int i = m - 1; i >= 0; --i) {
                h -= dungeon[i][n - 1];
                if (h <= 0) h = 1;
                hp[i][n - 1] = h;
            }
            h = hp[m - 1][n - 1];
            for (int j = n - 2; j >= 0; --j) {
                h -= dungeon[m - 1][j];
                if (h <= 0) h = 1;
                hp[m - 1][j] = h;
            }
            for (int i = m - 2; i >= 0; --i) {
                for (int j = n - 2; j >= 0; --j) {
                    h = Math.min(hp[i + 1][j], hp[i][j + 1]) - dungeon[i][j];
                    if (h <= 0) h = 1;
                    hp[i][j] = h;
                }
            }
            return hp[0][0];
        }
    

Log in to reply
 

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