Ac solution code


  • 1

    Solutino1. Bottom-Up DP - Runtime = O(nm); Space = O(nm)

    Iterate from last row to first row:
    2-D table for the minimum DP.
    h[i][j] is the minimum helth to enter (i, j) 
    h[0][0] is the anwser.	
    

    JAVA Code:

    public int calculateMinimumHP(int[][] A) {
    	int n = A.length, m = A[0].length;
    	int dp[][] = new int[n][m];// dp[i][j]: minimum hp to enter (i, j) 
    	
    	dp[n-1][m-1] = Math.max(-A[n-1][m-1], 0) + 1;// right-bottom node    	
    	for (int i = n - 2; i >= 0; i--) // last row
    		dp[i][m-1] = Math.max(1, dp[i+1][m-1] - A[i][m-1]);    	
    	for (int j = m - 2; j >= 0; j--) // last column
    		dp[n-1][j] = Math.max(1, dp[n-1][j+1] - A[n-1][j]);
    	
    	for (int i = n - 2; i >= 0; i--) {// calculate dp table
    		for (int j = m - 2; j >= 0; j--) {
    			dp[i][j] = Math.min(dp[i][j+1], dp[i+1][j]);// right, down
    			dp[i][j] = Math.max(1, dp[i][j] - A[i][j]);
    		}
    	}     	
        return dp[0][0];
    }
    

    Solution2. Memorized DFS

    Regular DFS without memorization will cause TLE error.

    public int calculateMinimumHP(int[][] A) {
    	int maxDamages[][] = new int[A.length][A[0].length];// KEY optimization: Memorization for the previous results
    	for (int i = 0; i < A.length; i++) Arrays.fill(maxDamages[i], Integer.MAX_VALUE);
    	
    	int maxDamage = DFS(A, 0, 0, maxDamages);
        return Math.max(0, -maxDamage) + 1;
    }
    
    int DFS(int[][] A, int i, int j, int maxDamages[][]) {// Total damage for one path
    	if (i > A.length - 1 || j > A[0].length - 1) return Integer.MIN_VALUE;    	
    	if (maxDamages[i][j] != Integer.MAX_VALUE) return maxDamages[i][j];// **Return the memorized result, to avoid duplicated DFS
    	
    	int maxDamage;
    	if (i == A.length - 1 && j == A[0].length - 1) {// Right-bottom node 	
    		maxDamage = A[i][j];
    	} else {
    		int right = DFS(A, i, j+1, maxDamages);
    		int down =  DFS(A, i+1, j, maxDamages);    	
    		maxDamage = Math.max(right, down) + A[i][j];// Choose the path with less damage: rightward, downward
    	}		
    	maxDamages[i][j] = Math.min(0, maxDamage);			
    	return maxDamages[i][j];
    }

Log in to reply
 

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