資料結構
網路
關係資料庫管理系統 (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 次
廣告