546. Remove Boxes

Problem Link

Tutorial

dp[l][r][k] means the maximum value of interval [l, r] with k repeating characters of boxes[r] at the back after r. The equation is dp(l, r, k) = max(dp(l, i, k + 1) + dp(i + 1, r - 1, 0)) for boxes[i] == boxes[r]. It means we remove [i+1, r - 1] first, and remove the repeating characters at the back with boxes[i] together.

Solution

#include <bits/stdc++.h>
using namespace std;

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

        int sqr(int a) {
            return a * a;
        }

        int dfs(int l, int r, int k, int dp[100][100][100]) {
            if (l > r) {
                return 0;
            }

            if (dp[l][r][k] != -1) {
                return dp[l][r][k];
            }

            int ret = 0;
            if (r - 1 >= 0 && boxes[r - 1] == boxes[r]) {
                ret = dfs(l, r - 1, k + 1, dp);
                dp[l][r][k] = ret;
                return ret;
            }
            ret = dfs(l, r - 1, 0, dp) + sqr(k + 1);
            for (int i = l; i < r; i++) {
                if (boxes[i] != boxes[r])
                    continue;
                ret = max(ret, dfs(l, i, k + 1, dp) + dfs(i + 1, r - 1, 0, dp));
            }
            dp[l][r][k] = ret;
            //printf("%d %d %d %d\n", l, r, k, ret);
            return ret;
        }
};