ระเบิดลูกโป่งในภาษา 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

• กำหนด dp อาร์เรย์ 2 มิติหนึ่งรายการของคำสั่ง n x n

• สำหรับการเริ่มต้น l :=n - 1 เมื่อ l>=0, ลด l ลง 1 ทำ −

  • สำหรับการเริ่มต้น r :=l เมื่อ r

    • สำหรับการเริ่มต้น i :=l เมื่อฉัน <=r เพิ่ม i โดย 1 ทำ −

      • y :=dp[i + 1, r] if i + 1

      • z :=a[l - 1] if l - 1>=0 มิฉะนั้น 1

      • w :=a[r + 1] if 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