删除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填充

  • return resolve(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