ระเบิดลูกโป่งใน C++ (Burst Balloons)

ภาพรวมปัญหา

มีลูกโป่ง n ลูก มีตัวเลขทับอยู่ ระเบิดลูก i ได้เหรียญ nums[i-1]×nums[i]×nums[i+1] หลังระเบิด ลูกข้างเคียงจะติดกัน หาเหรียญสูงสุด

ตัวอย่าง

[3,1,5,7] → 148
ระเบิด 1: 3×1×5=15 → [3,5,7]
ระเบิด 5: 3×5×7=105 → [3,7]
ระเบิด 3: 1×3×7=21 → [7]
ระเบิด 7: 1×7×1=7 → Total: 148

วิธีแก้ปัญหา: DP บนช่วง (Interval DP)

dp[l][r] = เหรียญสูงสุดจากการระเบิดลูกโป่งในช่วง [l,r] ทั้งหมด
พิจารณาลูกสุดท้ายที่ระเบิดในช่วงเป็น i: dp[l][r] = max(dp[l][i-1] + dp[i+1][r] + nums[l-1]×nums[i]×nums[r+1])

โค้ด C++

#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++) {
                    int left = (i-1 >= 0 ? dp[l][i-1] : 0);
                    int right = (i+1 < n ? dp[i+1][r] : 0);
                    int leftVal = (l-1 >= 0 ? a[l-1] : 1);
                    int rightVal = (r+1 < n ? a[r+1] : 1);
                    dp[l][r] = max(dp[l][r], left + right + leftVal * rightVal * a[i]);
                }
            }
        }
        return dp[0][n-1];
    }
};

int main() {
    Solution ob;
    vector<int> v = {3,1,5,7};
    cout << (ob.maxCoins(v));
}

ผลลัพธ์

148

การวิเคราะห์ความซับซ้อน

• เวลา: O(n³)
• พื้นที่: O(n²)