leetcode 546

问题

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
[1, 3, 2, 2, 2, 3, 4, 3, 1]

Output:

1
23

Explanation:

1
2
3
4
5
[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.

分析

dp[i][j][k] max score of subarray b[i] ~ b[j] if there are k boxes that have the same color as b[j] following b[j].

Those k boxes are from box[j+1] ~ box[n], to simulate boxes with other colors are removed first.

“ABACA”, dp[0][0][2] = dfs("A|AA") = 9 # B,C are removed

Base case: 0, if j < i

Transition:

dp[i][j][k] = dp[i][j-1][0] + (k+1)^2 # case 1

dp[i][j][k] = dp[i][p][k+1] + dp[p+1][j-1][0] # case 2

Case 1: drop box[j], remove k+1 boxes.

Case 2: Try all breakpoints p, attach a[j] to a[p], i <= p < j, box[p] == box[j]

Ans: dp[0][n-1][0]

时间复杂度：$O(n^4)$，空间复杂度：$O(n^3)$

https://www.youtube.com/watch?v=wT7aS5fHZhs&pbjreload=10

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 无优化  220ms
class Solution {
public:
    int m[101][101][101];
    int removeBoxes(vector<int>& boxes) {
        memset(m, 0, sizeof(m));
        return dfs(boxes, 0, boxes.size()-1, 0);
    }
    int dfs(vector<int> &boxes, int i, int j, int k) {
        if (i > j) return 0;
        if (m[i][j][k] != 0) return m[i][j][k];
        
        int ret = dfs(boxes, i, j-1, 0) + (k+1)*(k+1);
        for (int p = j-1; p >= i; --p) {
            if (boxes[p] == boxes[j]) {
                ret = max(ret, dfs(boxes, i, p, k+1) + dfs(boxes, p+1, j-1, 0));
            }
        }
        
        return m[i][j][k] = ret;
    }
};

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 优化1 20ms
// 另：m比较稀疏的情况下，使用hashmap比较节省空间
class Solution {
public:
    int m[101][101][101];
    int removeBoxes(vector<int>& boxes) {
        memset(m, 0, sizeof(m));
        return dfs(boxes, 0, boxes.size()-1, 0);
    }
    int dfs(vector<int> &boxes, int i, int j, int k) {
        if (i > j) return 0;
        if (m[i][j][k] != 0) return m[i][j][k];
        while (j > i && boxes[j-1] == boxes[j]) {
            j--;
            k++;
        }
        int ret = dfs(boxes, i, j-1, 0) + (k+1)*(k+1);
        for (int p = j-1; p >= i; --p) {
            if (boxes[p] == boxes[j]) {
                ret = max(ret, dfs(boxes, i, p, k+1) + dfs(boxes, p+1, j-1, 0));
            }
        }
        
        return m[i][j][k] = ret;
    }
};