DP solution of this problem?


  • 0
    F

    I know this problem can be easily solved with two pointers with better performance.
    But I guess it can be solved with DP too. However, I can't formulate the general equation of DP.
    Can anyone give me a hint here?


  • 0
    S

    The method below might not be the simplest way to do it, but I think it can work. Correct me if there is anything wrong.

    L(i) means the max area ends with height(i)

    So, L(i)=

      L(i-1)
      or
      (i-x)*Math.min(height[i],height[x])  //the greatest result for all x=0...(i-1)
    

    L(i) should be the bigger one of these two.


  • 0
    I

    Below is a DP solution. I dont know why its taking long time ?

    private int max(int a, int b, int c) {
    	return a > b? a > c ? a : c : b > c? b : c;
    }
    
    private int min(int a, int b) {
    	return a < b ? a : b;
    }
    
    private int maxAreaUtil(int[] height, int left, int right, int[][] memo) {
    	
    	if(left == right) {
    		return 0;
    	}
    	if(memo[left][right] == 0) {
    		int area = (right-left)*min(height[left], height[right]);
    		memo[left][right] = area;
    	}
    	
    	return max(maxAreaUtil(height, left + 1, right, memo), maxAreaUtil(height, left, right - 1, memo), memo[left][right]);
    }
    
    public int maxArea(int[] height) {
        int[][] memo = new int[height.length][height.length];
    	return maxAreaUtil(height, 0, height.length-1, memo);
    }
    

  • 0

    This method still need O(N^2)..


Log in to reply
 

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