資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的氣球爆裂問題
假設我們有 n 個氣球，它們從 0 到 n-1 索引。每個氣球上都塗有一個數字，用一個名為 nums 的陣列表示。我們必須爆破所有氣球。如果我們爆破氣球 i，我們將獲得 nums[i – 1] * nums[i] * nums[i + 1] 個硬幣。爆破後，i – 1 和 i + 1 則變為相鄰。我們必須找到透過明智地爆破氣球來收集的最大硬幣數量。
因此，如果輸入類似於 [3,1,5,7]，則結果將為 148。最初陣列類似於 [3,1,5,7]，然後在爆破 1 後，我們將得到 3 * 1 * 5 = 15，然後陣列為 [3,5,7]，然後爆破 5，所以我們將得到 (3 * 5 * 7) = 105，然後陣列類似於 [3,7]，然後爆破 3，所以我們將得到 (1*3*7) = 21，最後陣列為 [7]，所以爆破後，我們將得到 7，所以總和為 15 + 105 + 21 + 7 = 148。
為了解決這個問題，我們將遵循以下步驟：
n := a 的大小
如果 (n 不為零) 為假，則
返回 0
定義一個大小為 n x n 的二維陣列 dp
初始化 l := n - 1，當 l >= 0 時，l 減 1：
初始化 r := l，當 r < n 時，r 加 1：
初始化 i := l，當 i <= r 時，i 加 1：
y := dp[i + 1, r] 如果 i + 1 < n，否則為 0
z := a[l - 1] 如果 l - 1 >= 0 否則為 1
w := a[r + 1] 如果 r + 1 < n 否則為 1
x := dp[l, i - 1] 如果 i - 1 > = 0，否則為 0 + y + (z * w * a[i])
dp[l, r] := dp[l, r] 和 x 的最大值
返回 dp[0, n - 1]
示例
讓我們看看下面的實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxCoins(vector<int>& a) {
int n = a.size();
if(!n)return 0;
vector < vector <int>> dp(n,vector <int> (n));
for(int l = n-1;l>=0;l--){
for(int r=l;r<n;r++){
for(int i =l;i<=r;i++){
dp[l][r] = max(dp[l][r],(i-1>=0?dp[l][i-1]:0) +(i+1<n?dp[i+1][r]:0)+((l-1>=0?a[l-1]:1 )*(r+1<n?a[r+1]:1)*a[i]));
}
}
}
return dp[0][n-1];
}
};
main(){
Solution ob;
vector<int> v = {3,1,5,7};
cout << (ob.maxCoins(v));
}輸入
[3,1,5,7]
輸出
148
364 次檢視
