題目網址：https://leetcode.cn/problems/burst-balloons/

題意：給一整數 array nums 表示所有氣球上的編號。

戳破第 i 個氣球, 可以獲得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬幣。其中 i - 1 和 i + 1 代表與 i 相鄰的兩個氣球之編號。若 i - 1 或 i + 1 超出了 nums 的邊界, 則將其看作是編號為 1 的氣球。

返回戳破所有氣球所能獲得的最大硬幣數。

注意：1 ≤ nums[i] ≤ 300

Solution：

想法：利用 DP

本題重點：

  • 與其考慮先射爆哪個氣球, 不如考慮最後射爆哪個氣球。因為如果是考慮先射爆哪個氣球, 這種方式無法確定當前左、右邊的氣球編號。
  • 若是考慮最後射爆哪個氣球, 則可以確定該氣球的左、右邊編號

1. 定義狀態：

  • dp[i][j]：在 nums[i:j] 中最後射爆 index = k 的氣球
  • 在射爆 idx = k 的氣球前, 必須先射爆 nums[i:(k-1)]、nums[(k+1):j] 區間中的氣球

2. 得到狀態轉移方程：

  • 由於 dp[i][j] 只保證 nums[i:j] 區間的氣球會被射爆, 且 idx = k 的氣球最後才會被射爆。也就是說, 當射爆 nums[k] 時, 它左邊氣球的 idx 必為 i - 1, 且右邊氣球的 idx 必為 j + 1 （區間外的沒被射爆, 故 k 之左、右邊為區間外的 idx）。因為 nums[i:(k-1)]、nums[(k+1):j] 區間的氣球都已經先被射爆
  • 狀態轉移方程：
    • last = nums[i - 1] * nums[k] * nums[j + 1]
    • dp[i][j] = max(dp[i][j], dp[i][k - 1] + dp[k + 1][j] + last)

3. 初始化：

  • dp[0][0]：沒有氣球時, 所能獲得的最大硬幣數為 0
  • dp[i][0]：沒有氣球時, 所能獲得的最大硬幣數為 0。其中, 1 ≤ i ≤ n + 1
  • dp[0][j]：由於要求最大值, 且 nums[i] > 0, 乘積一定 > 0, 故都先初始化成 0。其中, 1 ≤ j ≤ n + 1
class Solution {
public:
    int maxCoins(vector<int>& nums) {
        const int n = nums.size();

        // 前、後各 insert 一個元素避免超出邊界
        nums.emplace(nums.begin(), 1);
        nums.emplace_back(1);

        vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));

        for (int len = 1; len <= n; ++len) { // len 為區間的長度
            for (int i = 1; i + len - 1 <= n; ++i) { // i 為區間的起始點
                const int j = i + len - 1; // j 為區間的終點
                for (int k = i; k <= j; ++k) { // k 用來遍歷區間 [i, j] 中的元素
                    const int last = nums[i - 1] * nums[k] * nums[j + 1];
                    dp[i][j] = max(dp[i][j], dp[i][k - 1] + dp[k + 1][j] + last);
                }
            }
        }

        return dp[1][n];
    }
};
  • time：$O(n^3)$ ➔ for loop, 其中 n 為氣球的數量
  • space：$O(n^2)$ ➔ dp