删除C ++中的框
假设我们有几个具有不同颜色的框，这些颜色用不同的正数表示。我们可以经历几轮移除盒子的过程，直到没有盒子剩下为止。在每个回合中，我们可以选择一些具有相同颜色的连续框（由k个框组成，k>=1），将其删除并得到k*k个点。因此，如果输入类似于−[[1,3,2,2,2,4,4,4,3,1]，那么输出将为21。
找到您可以获得的最高积分。
为了解决这个问题，我们将遵循以下步骤-
定义一个函数solve()，它将使用一个数组框，即i，j，k，一个3D数组dp，
如果i>j，则-
返回0
如果dp[i，j，k]不等于-1，则-
返回dp[i，j，k]
ret：=-inf
用于检查条件i+1<=j并且box[i+1]与box[i]相同，更新（将i增加1），（将k增加1），什么都不做-
ret：=ret的最大值和（k+1）*（k+1）+调用函数solve（boxes，i+1，j，0，dp）
对于初始化x：=i+1，当x<=j时，更新（将x增加1），-
ret：=ret和solve（（boxes，i+1，x-1，0，dp）+solve（boxes，x，j，k+1，dp））的最大值
如果box[x]与box[i]相同，则-
返回dp[i，j，k]=ret
在主要方法中，执行以下操作
n：=盒子大小
定义一个顺序为（n+1）x（n+1）x（n+1）的3D数组dp，并用-1填充
returnresolve(boxes,0,n-1,0,dp)
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(vector <int>& boxes, int i, int j, int k, vector < vector < vector <int > > >& dp){
if(i > j) return 0;
if(dp[i][j][k] != -1) return dp[i][j][k];
int ret = INT_MIN;
for(; i + 1 <= j && boxes[i + 1] == boxes[i]; i++, k++);
ret = max(ret, (k + 1) * (k + 1) + solve(boxes, i + 1, j, 0, dp));
for(int x = i + 1; x <= j; x++){
if(boxes[x] == boxes[i]){
ret = max(ret, solve(boxes, i + 1, x - 1, 0, dp) + solve(boxes, x, j, k + 1, dp));
}
}
return dp[i][j][k] = ret;
}
int removeBoxes(vector<int>& boxes) {
int n = boxes.size();
vector < vector < vector <int > > > dp(n + 1, vector < vector <int> > (n + 1, vector <int>(n + 1, -1)));
return solve(boxes, 0, n - 1, 0, dp);
}
};
main(){
Solution ob;
vector<int> v = {1,3,2,2,2,4,4,3,1};
cout << (ob.removeBoxes(v));
}输入项
{1,3,2,2,2,4,4,3,1}输出结果
21