clean 3ms Java DP solution


  • 0
    Q

    The idea is to start build from the destination. hp[i][j] means the minimal hp needed to move from cell [i,j] to destination.

    Since we can also build the matrix line by line, the space complexity can be reduced to the length of each line and we use hp[j] in line i to stand for the cell hp[i][j]

    Whenever the "minimal hp needed to reach the destination" become negtive or zero, reset the cell to 1, which means when reach this cell, the minimal hp should be 1.

    public int calculateMinimumHP(int[][] dungeon) {
        int M = dungeon.length;
        int N = dungeon[0].length;
        int[] hp = new int[N];
        
        hp[N-1] = (dungeon[M-1][N-1] <= 0) ? 1-dungeon[M-1][N-1] : 1;
        for(int j = N-2; j >= 0; --j){
            hp[j] = (hp[j+1] - dungeon[M-1][j] <= 0) ? 1 : hp[j+1] - dungeon[M-1][j];
        }
        
        for(int i = M-2; i >= 0; --i){
            hp[N-1] = (hp[N-1] - dungeon[i][N-1] <= 0) ? 1 : hp[N-1] - dungeon[i][N-1];
            for(int j = N-2; j >= 0; --j){
                int hpfromr = (hp[j+1] - dungeon[i][j] <= 0) ? 1 : hp[j+1] - dungeon[i][j];
                int hpfromd = (hp[j] - dungeon[i][j] <= 0) ? 1 : hp[j] - dungeon[i][j];
                hp[j] = (hpfromr > hpfromd) ? hpfromd : hpfromr;
            }
        }
    
        return hp[0];
    }

Log in to reply
 

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