題目來源
一個數(shù)組抱环，里面不同的數(shù)字，然后每次取連續(xù)的k個同樣數(shù)字菜皂，得分k*k贞绵，然后問怎么取得分最高。
沒想到怎么用DP來做恍飘，感覺這個確實很難想榨崩。
memo[l][r][k]表示有k個后綴和nums[r]一樣的情況下l到r得分最大谴垫。
memo[l][r][k] = max(memo[l][r][k], memo[l][i][k+1], memo[i+1][r-1][0])。
解釋的不太清楚母蛛，大家可以直接看討論區(qū)翩剪。
最后輸出的結(jié)果是memo[0][n-1][0]。
class Solution {
public:
int removeBoxes(vector<int>& boxes) {
int memo[100][100][100] = {0};
return dfs(boxes, memo, 0, boxes.size()-1, 0);
}
int dfs(vector<int>& boxes, int memo[100][100][100], int l, int r, int k)
{
if (l > r)
return 0;
if (memo[l][r][k] != 0)
return memo[l][r][k];
while (r > l && boxes[r] == boxes[r-1]) {
r--;
k++;
}
memo[l][r][k] = dfs(boxes, memo, l, r-1, 0) + (k + 1) * (k + 1);
for (int i=l; i<r; i++) {
if (boxes[i] == boxes[r])
memo[l][r][k] = max(memo[l][r][k], dfs(boxes, memo, l, i, k + 1) + dfs(boxes, memo, i + 1, r - 1, 0));
}
return memo[l][r][k];
}
};
