提醒：本文已翻新

本文已於 2026-06-23 翻新，原文可見 🔗 LeetCode 🔴 312. Burst Balloons (Old)

🔗 🔴 312. Burst Balloons

Problem Statement

題目簡述

給定一排氣球，每個氣球上有一個數字。每次戳破某個氣球，可以得到「它當下左右相鄰氣球的數字」與「自己數字」三者相乘的硬幣數；如果某側已經沒有氣球，視為那側有一個數字為 11 的邊界氣球。求戳破所有氣球後最多可以得到多少硬幣。

Constraints

約束條件

  • 1≤nums.length≤3001 \leq nums.length \leq 300
  • 0≤nums[i]≤1000 \leq nums[i] \leq 100

Input

一個整數陣列 numsnums，表示每個氣球上的數字。

Output

回傳一個整數，表示可以獲得的最大硬幣數。

Example

Input 1

1
nums = [3, 1, 5, 8]

Output 1

1
167
解釋

一種最佳順序是先戳破數字 11 的氣球，再戳破 55、33、88，總收益為 3×1×5+3×5×8+1×3×8+1×8×1=1673 \times 1 \times 5 + 3 \times 5 \times 8 + 1 \times 3 \times 8 + 1 \times 8 \times 1 = 167。

Note

邊界外的氣球只是在計算時視為數字 11，不需要真的被戳破。

思路：倒序戳氣球 + 動態規劃(DP)

由於按照順序戳氣球需要維護氣球的狀態，所以我們可以 倒序 戳氣球，這樣就不需要維護氣球的狀態。

關鍵觀察

由於會存在只剩下一個氣球的情況，我們在陣列的頭尾加上 11，這樣就可以確保每個氣球的左右邊界都有值。

假設在範圍 (l,r)(l, r) 中，最後一個戳破的氣球是第 ii 個氣球，那麼我們可以將問題分成兩個子問題：

  • 戳破第 ii 個氣球左邊的所有氣球，即問題變成戳破 (l,i)(l, i) 中的氣球。
  • 戳破第 ii 個氣球右邊的所有氣球，即問題變成戳破 (i,r)(i, r) 中的氣球。

因此可以令 f(l,r)f(l, r) 表示戳破開區間 (l,r)(l, r) 中的氣球所能獲得的最多硬幣數量，則可以寫出以下轉移式：

f(l,r)=max⁡l<i<r{f(l,i)+f(i,r)+nums[l]×nums[i]×nums[r]}f(l, r) = \max_{l < i < r} \{f(l, i) + f(i, r) + nums[l] \times nums[i] \times nums[r]\}

藉此，我們便能使用 動態規劃 (DP) 的方式來解決問題。

方法一：記憶化搜尋 / Top-down DP

從整個補邊後的區間開始遞迴，枚舉最後戳破的氣球，將左右兩側交給子問題處理。當兩個邊界相鄰（r−l≤1r - l \leq 1）時，中間已經沒有氣球可戳，收益為 00。

這種寫法最貼近上面的推導：先定義問題，再把問題拆成更小的同型問題。由於同一個區間會被不同分割方式反覆問到，所以需要用 記憶化搜尋 (Memoization) 將計算過的結果存起來，避免重複計算。在 Python 中可以使用 @cache，在 C++ 中則用一個二維陣列儲存。

正確性說明

正確性來自「最後一次操作」的枚舉完備性。任何合法戳法在一個區間內都必然有最後被戳破的氣球；固定這個氣球後，左右兩側的最優解可以獨立相加，所以枚舉所有可能的最後氣球並取最大值，就覆蓋了所有最優方案。

複雜度分析

  • 時間複雜度：O(n3)\mathcal{O}(n^3)，共有 O(n2)\mathcal{O}(n^2) 個區間狀態，每個狀態需要枚舉最後戳破的位置。
  • 空間複雜度：O(n2)\mathcal{O}(n^2)，用於記憶化所有區間狀態，遞迴深度最多為 O(n)\mathcal{O}(n)。

方法二：填表法 / Bottom-up DP

同樣的狀態也可以用 填表法 (Tabulation) 由短區間推到長區間。因為一個區間會依賴兩個更短的子區間，所以填表時先處理長度較短的區間，再逐步擴大到整個陣列。

具體來說，最短需要計算的有效區間長度是 33：左右兩個邊界中間剛好有一個氣球。接著枚舉更長的區間，對每個區間枚舉最後戳破的位置，套用同一個轉移式更新最大收益。

為什麼從短區間開始？

轉移需要左右兩側的答案，而這兩側一定比原區間更短。只要按照區間長度由小到大填表，計算目前區間時，它依賴的狀態就都已經算好了。

複雜度分析

  • 時間複雜度：O(n3)\mathcal{O}(n^3)，區間數量為 O(n2)\mathcal{O}(n^2)，每個區間枚舉一個分割位置。
  • 空間複雜度：O(n2)\mathcal{O}(n^2)，用於保存所有區間狀態。

總結

區間 DP 的反向思考模型

核心思路是「固定最後一次操作」的區間 DP。當操作會改變相鄰關係、合併關係或邊界關係時，不妨倒過來想：最後一次操作發生時，哪些資訊會變成固定邊界？這與矩陣鏈乘法、戳氣球、切木棍等問題共享相同的模型。

Code

方法一：記憶化搜尋 / Top-down DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        n = len(nums)
        nums = [1] + nums + [1]  # add 1 to both ends

        @cache
        def dfs(left: int, right: int) -> int:
            if right - left <= 1:
                return 0
            res = 0
            for i in range(left + 1, right):
                res = max(
                    res,
                    dfs(left, i) + dfs(i, right) + nums[left] * nums[i] * nums[right],
                )
            return res

        return dfs(0, n + 1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        vector<int> arr(n + 2, 1);
        for (int i = 1; i <= n; i++) arr[i] = nums[i - 1];

        vector<vector<int>> memo(n + 2, vector<int>(n + 2, -1));
        function<int(int, int)> dfs = [&](int left, int right) -> int {
            if (right - left <= 1) return 0;
            if (memo[left][right] != -1) return memo[left][right];
            int res = 0;
            for (int i = left + 1; i < right; i++) {
                int cur = arr[left] * arr[i] * arr[right];
                cur += dfs(left, i) + dfs(i, right);
                res = max(res, cur);
            }
            return memo[left][right] = res;
        };

        return dfs(0, n + 1);
    }
};

方法二：填表法 / Bottom-up DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        n = len(nums)
        nums = [1] + nums + [1]
        f = [[0] * (n + 2) for _ in range(n + 2)]
        for ln in range(1, n + 1):  # number of balloons inside (l, r)
            for l in range(n - ln + 1):
                r = l + ln + 1
                for m in range(l + 1, r):
                    f[l][r] = max(
                        f[l][r],
                        f[l][m] + f[m][r] + nums[l] * nums[m] * nums[r],
                    )
        return f[0][n + 1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        vector<int> arr(n + 2, 1);
        for (int i = 1; i <= n; i++) arr[i] = nums[i - 1];

        vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
        for (int length = 3; length <= n + 2; length++) {
            for (int left = 0; left <= n + 2 - length; left++) {
                int right = left + length - 1;
                for (int i = left + 1; i < right; i++) {
                    int cur = dp[left][i] + dp[i][right] +
                              arr[left] * arr[i] * arr[right];
                    dp[left][right] = max(dp[left][right], cur);
                }
            }
        }

        return dp[0][n + 1];
    }
};

寫在最後

Cover Image Credit

The cover image was created by @たろたろ. All rights belong to the original artist.

It is used here only as a non-commercial cover illustration for this note. I do not claim ownership of the artwork.

If you are the copyright holder and believe this usage is inappropriate, please contact me by email or leave a comment. I will remove the image promptly.

事實上，這題也可以視為是 Matrix Chain Multiplication 的變形題，只需要在最前面和最後面加上一個 11，並且從取 min⁡\min 改為取 max⁡\max 即可。