C ++中的爆破气球
因此，如果输入类似于[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：=一个的大小
如果（n为非零）为假，则，
返回0
定义一个nxn阶的2D数组dp
用于初始化l：=n-1，当l>=0时，将l减1做-
用于初始化i：=l，当i<=r时，将i加1做-
y：=dp[i+1，r]如果i+1<n，否则为0
z：=a[1-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的最大值
对于初始化r：=l，当r<n时，将r增加1做-
返回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