假设我们有几个具有不同颜色的框,这些颜色用不同的正数表示。我们可以经历几轮移除盒子的过程,直到没有盒子剩下为止。在每个回合中,我们可以选择一些具有相同颜色的连续框(由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