# Java DP + Memorization 60ms

• When facing this problem, I am keeping thinking how to simulate the case when `boxes[i] == boxes[j]` when `i` and `j` are not consecutive. It turns out that the dp matrix needs one more dimension to store such state. So we are going to define the state as

``````dp[i][j][k] represents the max points from box[i] to box[j] with k boxes whose values equal to box[i]
``````

The transformation function is as below

``````dp[i][j][k] = max(dp[i+1][m-1][1] + dp[m][j][k+1]) when box[i] = box[m]
``````

So the Java code with memorization is as below. Kindly ask me any questions.

``````  public int removeBoxes(int[] boxes) {
if (boxes == null || boxes.length == 0) {
return 0;
}

int size = boxes.length;
int[][][] dp = new int[size][size][size];

return get(dp, boxes, 0, size-1, 1);
}

private int get(int[][][] dp, int[] boxes, int i, int j, int k) {
if (i > j) {
return 0;
} else if (i == j) {
return k * k;
} else if (dp[i][j][k] != 0) {
return dp[i][j][k];
} else {
int temp = get(dp, boxes, i + 1, j, 1) + k * k;

for (int m = i + 1; m <= j; m++) {
if (boxes[i] == boxes[m]) {
temp = Math.max(temp, get(dp, boxes, i + 1, m - 1, 1) + get(dp, boxes, m, j, k + 1));
}
}

dp[i][j][k] = temp;
return temp;
}

}
``````

• @wihoho2

Well, finally one non TLE solution. I considered to use DP and noticed 3 dimension is needed. But it is really rare to see that lol. Good DP solution!

• Hi, I am not very sure why dp[0][size - 1][1] should be the final answer? Why k = 1 here? I thought we would take max score out of all the k in dp[0][size - 1][k]

dp[i][j][k] represents the max points from box[i] to box[j] with k boxes whose values equal to box[i]

However, I think dp[i][j][k] should mean the max points from box[i] to box[j] with k boxes of value box[i] merged.

And also the DP

We have two condition

1. We choose to merge k boxes

this mean we would have score = dp(i+1, j, 1) + k * k ...............(1)

1. We don't merge k boxes
so, we can continue to find box which is the same
this means when we find box m equal to box i, we can have one more box, so k become k + 1
So we have dp(i+1, m-1, 1) + dp (m, j, k + 1) ...............(2)
the first term is the other boxes
and the second term contain information of the same boxes(box[i] or box[m]) we have found till now

dp[i][j][k] = max ((1), (2))

• Nice solution, I was finding hard to simulate this in code.

what is the time complexity of this? is it n!?

• Thanks for sharing.
But 3-dimensional DP....
could anyone kindly tell me which company asks this Q? Is this an interview question for new grads?

• This post is deleted!

• This post is deleted!

• This post is deleted!

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