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이 아님) 거짓이면
- 0 반환
n x n 차수의 2D 배열 dp 하나 정의
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] 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]

C++의 풍선 버스트

예시

입력

출력