Burst Balloons trong C ++

Giả sử chúng ta có n bong bóng bay, chúng được đánh chỉ mục từ 0 đến n-1. Ở đây mỗi quả bóng được vẽ với một số trên đó được biểu thị bằng một mảng được gọi là nums. chúng ta phải làm nổ tất cả các quả bóng bay. Nếu chúng ta nổ bong bóng, chúng ta sẽ nhận được nums [i - 1] * nums [i] * nums [i + 1] số xu. Sau cụm từ, i - 1 và i + 1 trở thành liền kề. Chúng ta phải tìm số xu tối đa để thu thập bằng cách làm nổ những quả bóng bay một cách khôn ngoan.

Vì vậy, nếu đầu vào là [3,1,5,7], thì kết quả sẽ là 148. Ban đầu mảng giống như [3,1,5,7], sau đó sau khi bùng nổ 1, chúng ta sẽ nhận được 3 * 1 * 5 =15, sau đó mảng là [3,5,7], sau đó bùng nổ 5, vì vậy chúng ta sẽ nhận được (3 * 5 * 7) =105, sau đó mảng giống như [3,7], sau đó bùng nổ 3, vì vậy chúng ta sẽ nhận được (1 * 3 * 7) =21, cuối cùng là mảng là [7], vì vậy sau khi nổ, chúng ta sẽ nhận được 7, vì vậy tổng là 15 + 105 + 21 + 7 =148.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của một

• nếu (n khác 0) là false, thì

  • trả về 0

• Xác định một dp mảng 2D có thứ tự n x n

• để khởi tạo l:=n - 1, khi l> =0, giảm l đi 1 do -

  • để khởi tạo r:=l, khi r

    • để khởi tạo i:=l, khi i <=r, hãy tăng i lên 1 do -

      • y:=dp [i + 1, r] nếu i + 1

      • z:=a [l - 1] nếu l - 1> =0 nếu không thì 1

      • w:=a [r + 1] nếu r + 1

      • x:=dp [l, i - 1] nếu i - 1> =0, nếu không thì 0 + y + (z * w * a [i])

      • dp [l, r]:=max của dp [l, r] và x

• trả về dp [0, n - 1]

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

[3,1,5,7]

Đầu ra

148