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

dp[i][j][k]代表從boxes[i...j]中，左邊已經有k個和boxes[i]一樣的顏色，能得到的最大分數。 DP state transition: dp[i][i - 1][k] = 0 dp[i][i][k] = (k + 1) * (k + 1) dp[i][j][k] = max( (k + 1) * (k + 1) + dp[i + 1][j][0], dp[i + 1][m - 1][0] + dp[m][j][k + 1 ] ), where i < m <= j && boxes[i] == boxes[m] 1. (k + 1) * (k + 1) + dp[i + 1][j][0]代表的是先把boxes[i] drop得到的分數再加上boxes[i + 1...j]的最大可能分數。 2. dp[i + 1][m - 1][0] + dp[m][j][k + 1]代表boxes[i]先留著，boxes[i...j]中有一個boxes[m]和boxes[i]顏色一樣，先drop boxes[i + 1...m - 1]，此時boxes[i]會和boxes[m]相鄰，如果boxes[m...j]已經有k個和boxes[m]一樣的顏色，這時左邊會再加上boxes[i]，所以k變成k + 1。

// Top-Down Dynamic Programming
// int helper(vector<int>& boxes, int i, int j, int k, int dp[100][100][100]) {
int helper(vector<int>& boxes, int i, int j, int k, vector<vector<vector<int> > >& dp) {
    if (i > j) return 0;
    if (dp[i][j][k] > 0) return dp[i][j][k];
    
    // Optimization: all boxes of the same color counted continuously from the first box should be grouped together
    for ( ; i + 1 <= j && boxes[i + 1] == boxes[i]; i++, k++);

    int res = (1 + k) * (1 + k) + helper(boxes, i + 1, j, 0, dp); // remove the i-th box
    for (int m = i + 1; m <= j; ++m) {
        if (boxes[m] == boxes[i]) {
            // max(T(i + 1, m - 1, 0) + T(m, j, k + 1)), i < m <= j && boxes[i] == boxes[m]
            res = max(res, helper(boxes, i + 1, m - 1, 0, dp) + helper(boxes, m, j, k + 1, dp));
        }
    }
    return dp[i][j][k] = res;
}
int removeBoxes(vector<int>& boxes) { // time: O(n^4); space: O(n^3)
    int n = boxes.size();
    // int dp[100][100][100] = {0};
    vector<vector<vector<int> > > dp(n, vector<vector<int> >(n, vector<int>(n, 0)));
    return helper(boxes, 0, n - 1, 0, dp);
}

// Bottom-Up Dynamic Programming
int removeBoxes(vector<int>& boxes) { // time: O(n^4); space: O(n^3)
    if (boxes.empty()) return 0;
    int n = boxes.size();
    // int dp[n][n][n] = {0};
    vector<vector<vector<int> > > dp(n, vector<vector<int> >(n, vector<int>(n, 0)));
    
    // Initialization
    for (int i = 0; i < n; ++i) {
        for (int k = 0; k <= i; ++k) {
            dp[i][i][k] = (1 + k) * (1 + k);
        }   
    }
    
    for (int l = 1; l < n; ++l) { // range length
        for (int j = l; j < n; ++j) { // right bound
            int i = j - l; // left bound
            for (int k = 0; k <= i; ++k) {
                // start from removal of the i-th box
                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 dp[0][n - 1][0];
}