## Monday, April 17, 2017

### LeetCode 546 - Remove Boxes

Related: Box Stacking Problem
https://leetcode.com/problems/remove-boxes
Given several boxes with different colors represented by different positive numbers.
You may experience several rounds to remove boxes until there is no box left. Each time you can choose some continuous boxes with the same color (composed of k boxes, k >= 1), remove them and get `k*k` points.
Find the maximum points you can get.
Example 1:
Input:
```[1, 3, 2, 2, 2, 3, 4, 3, 1]
```
Output:
```23
```
Explanation:
```[1, 3, 2, 2, 2, 3, 4, 3, 1]
----> [1, 3, 3, 4, 3, 1] (3*3=9 points)
----> [1, 3, 3, 3, 1] (1*1=1 points)
----> [1, 1] (3*3=9 points)
----> [] (2*2=4 points)
```
Note: The number of boxes `n` would not exceed 100.
X.
http://www.lydxlx.net/2017/03/26/first-post/
The above DP solution seems to run in  time as there are  states for  and each state roughly takes  time in average to transit. However, the bound is not tight, and the tight one is , which can be shown via a more careful analysis.
We cluster  into several clusters based on the the value of . Say there are in total  clusters, and the -cluster contains  indices of . We then have . When we fix a cluster, there can be at most different states involved. Since different clusters are disjoint, the total number of meaningful states is also bounded by .

http://www.cnblogs.com/grandyang/p/6850657.html

```    int removeBoxes(vector<int>& boxes) {
int n = boxes.size();
int dp[100][100][100] = {0};
return helper(boxes, 0, n - 1, 0, dp);
}
int helper(vector<int>& boxes, int i, int j, int k, int dp[100][100][100]) {
if (j < i) return 0;
if (dp[i][j][k] > 0) return dp[i][j][k];
int res = (1 + k) * (1 + k) + helper(boxes, i + 1, j, 0, dp);
for (int m = i + 1; m <= j; ++m) {
if (boxes[m] == boxes[i]) {
res = max(res, helper(boxes, i + 1, m - 1, 0, dp) + helper(boxes, m, j, k + 1, dp));
}
}
return dp[i][j][k] = res;
}```
https://discuss.leetcode.com/topic/84300/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]``
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))
``````  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;
}

}``````
X.
http://www.codingblog.cn/blog/34458.html
http://blog.csdn.net/yy254117440/article/details/67638980

````   1 2 3 4 2 2 `
1

1

```

``````   1 2 3 4 2 2
i       j   即dp[i][j][1]```
1
2

1
2

```

````dfs(boxes, mem, l, r - 1, 0 ) + (k + 1) * (k + 1);`
1

1

```

``````   1 2 2 2 左右两部分合并
i j    dp[i][j][2]
3 4    中间的部分
i j    dp[i][j][0]```
1
2
3
4

1
2
3
4

```
````Math.max(mem[l][r][k], dfs(boxes, mem, l, i, k + 1) + dfs(boxes, mem, i + 1, r - 1, 0));`
```
public int removeBoxes(int[] boxes) { int size = boxes.length; int[][][] mem = new int[size][size][size]; return dfs(boxes, mem, 0, size - 1, 0); } private int dfs(int[] boxes, int[][][] mem, int l, int r, int k) { if (l > r) return 0; if (mem[l][r][k] > 0) return mem[l][r][k]; while (r > l && boxes[r] == boxes[r - 1]) { r--; k++; } mem[l][r][k] = dfs(boxes, mem, l, r - 1, 0 ) + (k + 1) * (k + 1); for (int i = l; i < r; i++) { if (boxes[i] == boxes[r]) { mem[l][r][k] = Math.max(mem[l][r][k], dfs(boxes, mem, l, i, k + 1) + dfs(boxes, mem, i + 1, r - 1, 0)); } } return mem[l][r][k]; }

http://www.codingblog.cn/blog/34458.html
``````    /* l: 最左位置
* r: 最右位置
* same_len : 在r后面且与r相同的元素的长度
* rec: 记录从l到r的后缀长度为same_len时的消除值
* boxes: 所有盒子的颜色值
* 返回最终的最大的盒子值
*/
int dfs(int l, int r, int same_len, int rec[100][100][100], vector<int>& boxes){
if(l>r) return 0;
// 已经遍历过不需要再遍历
if(rec[l][r][same_len] > 0)
return rec[l][r][same_len];
while(r>l && boxes[r] == boxes[r-1]){
r--;
same_len++;
}
rec[l][r][same_len] = (same_len+1)*(same_len+1) + dfs(l,r-1,0,rec,boxes);
for(int i = l; i < r;i++)
if(boxes[i] == boxes[r])
// 如果发现这个值跟最右的值相等，存在两种可能
// 先消除最右的元素及其后缀元素的长度
// 消除当前值和最右值中间的元素再消除相同的元素值和当前元素值前面的元素
rec[l][r][same_len] = max(rec[l][r][same_len], dfs(l,i,same_len+1,rec,boxes)+dfs(i+1,r-1,0,rec,boxes));

return rec[l][r][same_len];

}``````
https://mikecoder.github.io/oj-code/2017/05/06/RemoveBoxes/
Think about using a DP[100][100][100] to store the status that from [left] to [right] we have [k] same numbers in the end.
So, we can find the status transition way:

http://www.cnblogs.com/heisenberg-/p/6789708.html
http://blog.csdn.net/raorang/article/details/72584957
memo[l][r][k] = max(memo[l][r][k], dfs(boxes,memo,l,i,k+1) + dfs(boxes,memo,i+1,r-1,0));

https://discuss.leetcode.com/topic/84687/java-top-down-and-bottom-up-dp-solutions
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;
}``````

X.

```    int removeBoxes(vector<int>& boxes) {
int n = boxes.size();
int dp[n][n][n] = {0};
for (int i = 0; i < n; ++i) {
for (int k = 0; k <= i; ++k) {
dp[i][i][k] = (1 + k) * (1 + k);
}
}
for (int t = 1; t < n; ++t) {
for (int j = t; j < n; ++j) {
int i = j - t;
for (int k = 0; k <= i; ++k) {
int res = (1 + k) * (1 + k) + dp[i + 1][j][0];
for (int m = i + 1; m <= j; ++m) {
if (boxes[m] == boxes[i]) {
res = 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];
}```

dp[l][r][k]表示第l到第r个合并后的盒子，连同其后颜色为color[r]的长度k一并消去所能得到的最大得分。
```dp[l][r][k] = dp[l][r - 1][0] + (length[r] + k) ** 2

dp[l][r][k] = max(dp[l][r][k], dp[l][i][length[r] + k] + dp[i + 1][r - 1][0])  其中 i ∈[l, r - 1]```