## Leetcode 546

Posted on 29 Mar 2017
dynamic programming

### 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;
}
};