Java top-down and bottom-up DP solutions


  • 44
    F

    Since the input is an array, let's begin with the usual approach by breaking it down with the original problem applied to each of the subarrays.

    Let the input array be boxes with length n. Define T(i, j) as the maximum points one can get by removing boxes of the subarray boxes[i, j] (both inclusive). The original problem is identified as T(0, n - 1) and the termination condition is as follows:

    1. T(i, i - 1) = 0: no boxes so no points.
    2. T(i, i) = 1: only one box left so the maximum point is 1.

    Next let's try to work out the recurrence relation. For T(i, j), take the first box boxes[i](i.e., box at index i) as an example. What are the possible ways of removing it? (Note: we can also look at the last box and the analyses turn out to be the same.)

    If it happens to have a color that you don't like, you'll probably say "I don't like this box so let's get rid of it now". In this case, you will first get 1 point for removing this "poor" box. But still you want maximum points for the remaining boxes, which by definition is T(i + 1, j). In total your points will be 1 + T(i + 1, j).

    But later after reading the rules more carefully, you realize that you might get more points if this box (boxes[i]) can be removed together with other boxes of the same color. For example, if there are two such boxes (including boxes[i]), you get 4 points by removing them simultaneously, instead of 2 by removing them one by one. So you decide to let it stick around a little bit longer until there is another box of the same color (whose index is m) becomes its neighbor. Note at this moment all boxes between indices i + 1 and m - 1 would have been removed. So if we again aim for maximum points, the points gathered so far will be T(i + 1, m - 1). What about the remaining boxes?

    For now, the boxes we left behind have two parts: the one at index i (boxes[i]) and those of the subarray boxes[m, j], with the former bordering the latter from the left. Apparently there is no way applying the definition of the subproblem to the subarray boxes[m, j], since we have some extra piece of information that is not included in the definition. In this case, I shall call that the definition of the subproblem is not self-contained and its solution relies on information external to the subproblem itself.

    Another example of problem that does not have self-contained subproblems is leetcode 312. Burst Balloons, where the maximum coins of subarray nums[i, j] depend on the two numbers adjacent to nums[i] on the left and to nums[j] on the right. So you may find some similarities between these two problems.

    Problems without self-contained subproblems usually don't have well-defined recurrence relations, which renders it impossible to be solved recursively. The cure to this issue can sound simple and straightforward: modify the definition of the problem to absorb the external information so that the new one is self-contained.

    So let's see how we can redefine T(i, j) to make it self-contained. First let's identify the external information. On the one hand, from the point of view of the subarray boxes[m, j], it knows nothing about the number (denoted by k) of boxes of the same color as boxes[m]to its left. On the other hand, given this number k, the maximum points can be obtained from removing all these boxes is fixed. Therefore the external information to T(i, j) is this k. Next let's absorb this extra piece of information into the definition of T(i, j) and redefine it as T(i, j, k) which denotes the maximum points possible by removing the boxes of subarray boxes[i, j] with k boxes attached to its left of the same color as boxes[i]. Lastly let's reexamine some of the statements above:

    1. Our original problem now becomes T(0, n - 1, 0), since there is no boxes attached to the left of the input array at the beginning.

    2. The termination conditions now will be:
      a. T(i, i - 1, k) = 0: no boxes so no points, and this is true for any k (you can interpret it as nowhere to attach the boxes).
      b. T(i, i, k) = (k + 1) * (k + 1): only one box left in the subarray but we've already got k boxes of the same color attached to its left, so the total number of boxes of the same color is (k + 1) and the maximum point is (k + 1) * (k + 1).

    3. The recurrence relation is as follows and the maximum points will be the larger of the two cases:
      a. If we remove boxes[i] first, we get (k + 1) * (k + 1) + T(i + 1, j, 0) points, where for the first term, instead of 1 we again get (k + 1) * (k + 1) points for removing boxes[i] due to the attached boxes to its left; and for the second term there will be no attached boxes so we have the 0 in this term.
      b. If we decide to attach boxes[i] to some other box of the same color, say boxes[m], then from our analyses above, the total points will be T(i + 1, m - 1, 0) + T(m, j, k + 1), where for the first term, since there is no attached boxes for subarray boxes[i + 1, m - 1], we have k = 0 for this part; while for the second term, the total number of attached boxes for subarray boxes[m, j] will increase by 1 because apart from the original k boxes, we have to account for boxes[i]now, so we have k + 1 for this term. But we are not done yet. What if there are multiple boxes of the same color as boxes[i]? We have to try each of them and choose the one that yields the maximum points. Therefore the final answer for this case will be: max(T(i + 1, m - 1, 0) + T(m, j, k + 1)) where i < m <= j && boxes[i] == boxes[m].

    Before we get to the actual code, it's not hard to discover that there is overlapping among the subproblems T(i, j, k), therefore it's qualified as a DP problem and its intermediate results should be cached for future lookup. Here each subproblem is characterized by three integers (i, j, k), all of which are bounded, i.e, 0 <= i, j, k < n, so a three-dimensional array (n by n by n) will be good enough for the cache.

    Finally here are the two solutions, one for top-down DP and the other for bottom-up DP. From the bottom-up solution, the time complexity will be O(n^4) and the space complexity will be O(n^3).

    Top-down DP:

    public int removeBoxes(int[] boxes) {
        int n = boxes.length;
        int[][][] dp = new int[n][n][n];
        return removeBoxesSub(boxes, 0, n - 1, 0, dp);
    }
        
    private int removeBoxesSub(int[] boxes, int i, int j, int k, int[][][] dp) {
        if (i > j) return 0;
        if (dp[i][j][k] > 0) return dp[i][j][k];
            
        int res = (k + 1) * (k + 1) + removeBoxesSub(boxes, i + 1, j, 0, dp);
            
        for (int m = i + 1; m <= j; m++) {
            if (boxes[i] == boxes[m]) {
                res = Math.max(res, removeBoxesSub(boxes, i + 1, m - 1, 0, dp) + removeBoxesSub(boxes, m, j, k + 1, dp));
            }
        }
            
        dp[i][j][k] = res;
        return res;
    }
    

    Bottom-up DP:

    public int removeBoxes(int[] boxes) {
        int n = boxes.length;
        int[][][] dp = new int[n][n][n];
        	
        for (int j = 0; j < n; j++) {
        	for (int k = 0; k <= j; k++) {
        	    dp[j][j][k] = (k + 1) * (k + 1);
        	}
        }
        	
        for (int l = 1; l < n; l++) {
        	for (int j = l; j < n; j++) {
        	    int i = j - l;
        	        
        	    for (int k = 0; k <= i; k++) {
        	        int res = (k + 1) * (k + 1) + dp[i + 1][j][0];
        	            
        	        for (int m = i + 1; m <= j; m++) {
        	            if (boxes[m] == boxes[i]) {
        	                res = Math.max(res, dp[i + 1][m - 1][0] + dp[m][j][k + 1]);
        	            }
        	        }
        	            
        	        dp[i][j][k] = res;
        	    }
        	}
        }
        
        return (n == 0 ? 0 : dp[0][n - 1][0]);
    }
    

    Side notes: In case you are curious, for the problem "leetcode 312. Burst Balloons", the external information to subarray nums[i, j] is the two numbers (denoted as left and right) adjacent to nums[i] and nums[j], respectively. If we absorb this extra piece of information into the definition of T(i, j), we have T(i, j, left, right) which represents the maximum coins obtained by bursting balloons of subarray nums[i, j] whose two adjacent numbers are left and right. The original problem will be T(0, n - 1, 1, 1) and the termination condition is T(i, i, left, right) = left * right * nums[i]. The recurrence relations will be: T(i, j, left, right) = max(left * nums[k] * right + T(i, k - 1, left, nums[k]) + T(k + 1, j, nums[k], right)) where i <= k <= j (here we interpret it as that the balloon at index k is the last to be burst. Since all balloons can be the last one so we try each case and choose one that yields the maximum coins). For more details, refer to dietpepsi 's post.


  • 1
    H

    Thank you for your detailed explanation !

    This problem and the burst balloon problem are of the same nature and they really hard problems.

    Your explanation presents us a structured thinking strategy to deal with these problems.


  • 0
    A

    This is the best explanation I have read so far and thanks for you help.


  • 0
    G

    Should I say T(i, j) = maxPoint gained from boxes[i:j] by removing all possible numbers of boxes[i] together


  • 0
    F

    @greedisgood-1000000 Hi greedisgood. Is this T(i, j) the original definition or the modified one? If it is the original one, then it should be the maximum points gained by removing all boxes from boxes[i:j]. If it is the modified one, you can say that it is the maximum points gained by removing all boxes from boxes[i:j] with all possible numbers of boxes that have the same color as boxes[i] attached to its left, i.e., T(i, j) = T(i, j, 0) + T(i, j, 1) + T(i, j, 2) + ....


  • 0
    Y
    This post is deleted!

  • 0
    This post is deleted!

  • 0
    L

    Thanks a lot !


  • 1
    M

    Trust me!!! Read this paragraph!!!
    I was kind of impatient when I first read the paragraph. I skipped a lot and chased only for the solution. Now it is the second time I read the whole story and I suddenly realized how much time I have wasted on these similar problems.


  • 0

    Great Solution and explanation! Add one simple optimization to beat 99%.
    Continuous same color boxes should always been used together

    public class Solution {
        public int removeBoxes(int[] boxes) {
            int n = boxes.length;
            //i, j, k store the max points from i to j, when there are k same color boxes (with i) adjacent to the left of i; 
            int[][][] dp = new int[n][n][n];
            return removeBoxes(boxes, 0, n-1, 0, dp);
        }
        
        private int removeBoxes(int[] boxes, int i, int j, int k, int[][][] dp){
            int n = boxes.length;
            //Base case
            if(j < i) {
                return 0;
            }else if (i == j){
                return (k+1)*(k+1);
            }else if (dp[i][j][k] > 0){
                return dp[i][j][k];
            }
            //recurrence
            int tmpK=k, tmpI=i;
            //continuous same color boxes should always been used together
            while(tmpI<=j && boxes[tmpI]==boxes[i]){
                tmpK++;
                tmpI++;
            }
            int res=tmpK*tmpK+removeBoxes(boxes, tmpI, j, 0, dp);
            for(int l=tmpI+1; l<=j; l++){
                if(boxes[l]==boxes[i] && boxes[l-1]!=boxes[i]){//continuous same color boxes should always been used together
                    res=Math.max(res, removeBoxes(boxes, tmpI, l-1, 0, dp)+
                               removeBoxes(boxes, l, j, tmpK, dp));
                }      
            }
            dp[i][j][k]=res;
            return res;
        }
    }
    

  • 0
    L

    Can I ask what is this step:

    if (dp[i][j][k] > 0) return dp[i][j][k];

    means? Will dp[i][j][k] be negative?
    The solution is so clear, thank you very much!


Log in to reply
 

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