C++でのバーストバルーン

n個のバルーンがあり、これらには0からn-1までのインデックスが付けられているとします。ここで、各バルーンには、numsと呼ばれる1つの配列で表される数字が描かれています。すべての風船を破裂させる必要があります。バルーン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がゼロ以外）がfalseの場合、

  • 0を返す

• 次数nxn

  の2D配列dpを1つ定義します。

• l：=n -1を初期化する場合、l> =0の場合、lを1減らしますdo-

  • r：=lを初期化する場合、r

    • i：=lを初期化する場合、i <=rの場合、iを1つ増やしますdo −

      • y：=dp [i + 1、r] i + 1

      • z：=a [l --1] if l --1>=0それ以外の場合1

      • w：=a [r + 1]（r + 1

      • x：=dp [l、i --1] if 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