DFS+Cache, beat 98.8%. Including transfer to DP & space optimize


  • 1

    DFS+Cache:

    public class Solution {
        int[][] cache;
        public int calculateMinimumHP(int[][] dungeon) {
            cache = new int[dungeon.length][dungeon[0].length];
            int ret = search(dungeon, 0, 0);
            return ret > 0 ? 1 : -ret + 1;
        }
        private int search(int[][] matrix, int x, int y) {
            if (x == matrix.length - 1 && y == matrix[0].length - 1) return matrix[x][y] > 0 ? 0 : matrix[x][y];
            if (x < 0 || y < 0 || x >= matrix.length || y >= matrix[0].length) return Integer.MIN_VALUE;
            if (cache[x][y] != 0) return cache[x][y] == -1 ? 0 : cache[x][y];
            
            int left = search(matrix, x + 1, y);
            int right = search(matrix, x, y + 1);
            int cur = matrix[x][y] + Math.max(left, right);
            
            cache[x][y] = cur > 0 ? -1 : cur;
            return cur > 0 ? 0 : cur;
        }
    }
    

    DP:

    public class Solution {
        public int calculateMinimumHP(int[][] dungeon) {
            int row = dungeon.length, col = dungeon[0].length;
            int[][] F = new int[row][col];
            for (int i = row - 1; i >= 0; i--) {
                for (int j = col - 1; j >= 0; j--) {
                    if (i == row - 1 && j == col - 1) F[i][j] = dungeon[i][j] > 0 ? 0 : dungeon[i][j];
                    else {
                        int left = i + 1 >= row ? Integer.MIN_VALUE : F[i + 1][j];
                        int right = j + 1 >= col ? Integer.MIN_VALUE : F[i][j + 1];
                        int cur = dungeon[i][j] + Math.max(left, right);
                        F[i][j] = cur > 0 ? 0 : cur;
                    }
                }
            }
            return F[0][0] > 0 ? 1 : -F[0][0] + 1;
        }
    }
    

    Space optimize to O(n):

    public class Solution {
        public int calculateMinimumHP(int[][] dungeon) {
            int row = dungeon.length, col = dungeon[0].length;
            int[][] F = new int[2][col];
            for (int i = row - 1; i >= 0; i--) {
                for (int j = col - 1; j >= 0; j--) {
                    if (i == row - 1 && j == col - 1) F[i % 2][j] = dungeon[i][j] > 0 ? 0 : dungeon[i][j];
                    else {
                        int left = i + 1 >= row ? Integer.MIN_VALUE : F[(i + 1) % 2][j];
                        int right = j + 1 >= col ? Integer.MIN_VALUE : F[i % 2][j + 1];
                        int cur = dungeon[i][j] + Math.max(left, right);
                        F[i % 2][j] = cur > 0 ? 0 : cur;
                    }
                }
            }
            return F[0][0] > 0 ? 1 : -F[0][0] + 1;
        }
    }
    

  • 0
    B

    Hi. Can you give some detailed explanation about your answer? I'm a little bit confused about your DFS+Cache solution and DP solution.

    I also come up with a DP solution, which is more complicated than you. So I hope you can give more explanation about your idea. Thx.


  • 0

    @biaoge could I know if you understand the DFS solution. My DP comes from the DFS. Would you want me to explain the DFS, or how to transfer the DFS to DP


  • 0
    B

    @lusoul hi, I wish you explain the DFS + Cache solution. If you could explain DFS solution, I think maybe I could transfer DFS to DP by myself. Thx


  • 0

    @biaoge
    0_1498777089550_WechatIMG115.jpeg
    比较需要注意的一点是,取left和right的最大值 + matrix[x][y]=cur, 如果cur是大于0的数,直接返回0即可,因为cur表示当前点最少需要的生命值,并不会影响到上一层,只有当cur<0时才会影响到上一层


Log in to reply
 

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