[LeetCode]: 546. Remove Boxes

https://leetcode.com/contest/leetcode-weekly-contest-25/problems/remove-boxes/

Solution:
This question is not easy. May use the dsf strategy, but the brutal force one cannot pass the OJ. One way to optimize it is to use memorization of the intermediate states. The parameters for the states needs include the range, the number of repeated elements, and the earned points. The range needs two parameters: the left and right. So we need a three-dimensional array to represent the states, and the value of it will be earned points. Let us dp[l][r][ct] represent the highest points earned in the range of l to r, where l is the left boundary, r is the right boundary, and ct is the number of repeated elements. The we need to calculate dp[0][n-1][0].

We can first calculate the dp[l][r][ct] = dsf(l+1, r, 0) + (ct+1)*(ct+1), which is equivalent to separate the original array into the first element and the rest ones;
Then is the key part:  since we need to find the maximum, we need to loop the whole array, and when the same elements as the first element is found, the transition equation can be wrote:
                 dp[l][r][ct] = max(dp[l][r][ct], dsf(l+1, i-1, 0) + dsf(i, r, ct+1)),  when arr[l] == arr[i].
where i is between l+1 and r. The second term in the max() is to divide the array into two parts: the first one is from l+1 to i-1 with 0 repeated elements; the other is from i to r with ct+1 repeated elements so far (arr[l] == arr[i]). (or the l element is now adjacent with the ith element.)

In order to reduce the complexity of the dsf, we can assign some unique initial value to dp[l][r][ct], for example, a negative value. Then when the dp[l][r][ct] becomes positive, it means it has already been calculated. So we can just use the calculated results directly. This is exactly how memorization works. See code below for details:

Code:

const int N = 100;
int dp[N][N][N];

class Solution {
public:
    int removeBoxes(vector<int>& boxes) {
        int n = boxes.size();
        memset(dp, -1, sizeof(dp));
        return dsf(boxes, 0, n-1, 0);
    }

    int dsf(vector<int> &b, int l, int r, int ct){
        if(l>r) return 0;
        int t = dp[l][r][ct];
        if(t!=-1) return t;
        t = dsf(b, l+1, r, 0) + (ct+1)*(ct+1);
        for(int i=l+1; i<=r; ++i){
            if(b[i]==b[l]) t=max(t, dsf(b, l+1, i-1, 0) + dsf(b, i, r, ct+1));
        }
        return dp[l][r][ct]=t;
    }
};