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：=一个的大小

• 如果（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