数据结构
网络
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 次查看
