数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中移除盒子
假设我们有几个不同颜色的盒子，这些颜色由不同的正数表示。我们可以进行几轮移除盒子，直到没有盒子剩下。每一轮我们可以选择一些颜色相同的连续盒子（由k个盒子组成，k >= 1），移除它们并获得k*k分。所以如果输入是 − [1,3,2,2,2,4,4,3,1]，那么输出将是21。
找到你能获得的最大分数。
为了解决这个问题，我们将遵循以下步骤：
- 定义一个函数 solve()，它将接收一个数组 boxes、i、j、k 和一个三维数组 dp。
- 如果 i > j，则：
- 返回 0
- 如果 dp[i, j, k] 不等于 -1，则：
- 返回 dp[i, j, k]
- ret := -inf
- 为了检查条件 i + 1 <= j 并且 boxes[i + 1] 与 boxes[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），执行：
- 如果 boxes[x] 与 boxes[i] 相同，则：
- ret := ret 和 solve((boxes, i + 1, x - 1, 0, dp) + solve(boxes, x, j, k + 1, dp)) 的最大值
- 如果 boxes[x] 与 boxes[i] 相同，则：
- 返回 dp[i, j, k] = ret
- 在主方法中，执行以下操作：
- n := boxes 的大小
- 定义一个 (n + 1) x (n + 1) x (n + 1) 阶的三维数组 dp，并将其填充为 -1
- 返回 solve(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
更新于：2020年6月1日
浏览量 150 次
广告