Java top-down and bottom-up DP solutions

• 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., the 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 dislike, 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, 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 up to this moment all boxes from index `i + 1` to index `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?

At this moment, the boxes we left behind consist of 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]` within subarray `boxes[i + 1, j]`? 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];

for (; i + 1 <= j && boxes[i + 1] == boxes[i]; i++, k++); // optimization: all boxes of the same color counted continuously from the first box should be grouped together
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.

• 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.

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

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

• @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) + ...`.

• This post is deleted!

• This post is deleted!

• Thanks a lot !

• 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.

• 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;
}
}
``````

• 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!

• @LEMO
I think it means dp[i][j][k] has been computed before. Otherwise, it will be 0.

• @Yu-Ho thank you

• (k + 1) * (k + 1) + T(i + 1, j, 0)

Hey @fun4LeetCode Thanks very much for such a wonderful detailed explanation. However I am still confused one thing in the article:

Follow definition of " 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]":

if we move boxes[i] first, why we could get (k + 1) * (k + 1) + T(i + 1, j, 0) points? I can understand (k + 1) * (k + 1) which represents points for removing boxes[i] immediately with its attached boxes to its left.

By this time, boxes[i+1] could be the same color with boxes[i] (which leads to scenario b.).

However, boxes[i+1] could also be different color from boxes[i]. But we don't know how many boxes attached to boexs[i+1] left of the same color as boxes[i+1]. It is possible we have scenarios like this :

``````[t0,... ......., t1, 0, 1, ....... k, boxed[i], boxed[i+1]
------------------  ----------- ---- --------  ----------
boxed[i+1]'s color  boxed[i]'s color
``````

In this case, how we could say if we move boxed[i] directly, one subproblme could be :(k + 1) * (k + 1) + T(i + 1, j, 0) ?
It seems that if we removed boxed[i] and its attached k same color boxed, there are also t boxes with the same color of boxed[i+1].

• @coder42 Hi coder42. The case in you example cannot happen according to the definition of `T(i, j, k)`. All the boxes to the left of `boxes[i]` can only have the same color as `boxes[i]`. There won't be multiple colors among those boxes.

• @fun4LeetCode Thanks for quickly reply!

I read through your post again and I think the reason "The case in you example cannot happen" is because the way you define `T(i, j, k)` naturally restricts that we only care the scenarios "where all the boxes to the left of boxes[i] can only have the same color as boxes[i]".

It is impossible to have multiple colors on those boxes if we follow the definition of `T(i, j, k)` , Right?

• @coder42 Correct. Also this is guaranteed by the recurrence relation of `T(i, j, k)` such that the case in your example won't happen.

• 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++) {
``````

This is a great solution! I understand the idea, but when come to implementation, how can I know how to organize the loop in this way? can anyone explain it a little bit more? thanks.

• @dong.li.3344 Hi dong.li.3344. As a rule of thumb, if you have a recurrence relation like `T(i, j) = T(i, k) + T(k, j)` with `i <= k <= j` (or something similar), then for the bottom up DP, you have to compute subproblems for subarrays with increasing length, i.e., first compute those of length of `1`, then length of `2`, next length of `3` and so on. This is because to get `T(i, j)` where the corresponding subarray has length of `j - i + 1`, we need information for `T(i, i)`, `T(i, i + 1)`, `T(i, i + 2)`, ..., `T(i, j - 1)` where the corresponding subarrays have length of `1`, `2`, `3`, ..., up to length of `j - i` (similar for those subarrays ending at `j`).

This is why in the outmost loop I have the variable `l` which indicates the length of the subarray. Inside the loop, I recovered the starting and ending indices of the subarray (that is, index `i` and `j`) so it's easier for us to apply the recurrence relation.

• @fun4LeetCode I have a question about the first top-bottom code. It is about the k. In the recursion, you change the k value and before the end of the recursion, you use the updated k as the index for updating dp array. The k here is not the same with the input. But when you use the dp array, you still use the original k. Won't this cause problem?
An example for that is: if 1 9 4 9 9 6.
When you save value for input (3, 5, 1) which is for (9, 9, 6) and the first 9 is attached with it. Before the end, you actually update the array (3, 5, 2) since k has been updated in this loop:

``````for (; i + 1 <= j && boxes[i + 1] == boxes[i]; i++, k++);
``````

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