Description
TL;DR 消消乐
给出一个数组\(boxes[0, n)\)，数组每个元素均为正整数。每一次操作可以从中消掉一些相同数值的元素，直至数组为空。每消除\(k\)个元素得到的贡献是\(k^2\)，求最大贡献
Constraints
- \(1 \le boxes.length \le 100\)
- \(1 \le boxes[i] \le 100\)
Solution
关键在于定义\(dp\)的含义：设\(dp[l][r][x]\)为区间\([l,r]\)且\(r\)右侧拥有与\(boxes[r]\)相同数值的\(x\)个元素
定义好就可以递推了
Code
class Solution {
public:
int removeBoxes(vector<int>& boxes) {
int dp[101][101][101];
memset(dp, 0, sizeof dp);
auto dfs = [&](auto &&dfs, int l, int r, int x) {
if(l == r) return (x+1) * (x+1);
if(l > r) return 0;
if(dp[l][r][x]) return dp[l][r][x];
// [l, r-1], [r, x...)
int ans = dfs(dfs, l, r-1, 0) + dfs(dfs, r, r, x);
for(int i = l; i < r; ++i) {
// [l, i], [i+1, r-1], [r, x...)
if(boxes[i] == boxes[r]) {
ans = max(ans, dfs(dfs, i+1, r-1, 0) + dfs(dfs, l, i, x+1));
} else {
ans = max(ans, dfs(dfs, l, i, 0) + dfs(dfs, i+1, r-1, 0) + dfs(dfs, r, r, x));
}
}
return dp[l][r][x] = ans;
};
return dfs(dfs, 0, boxes.size()-1, 0);
}
};