🔗 🔴 312. Burst Balloons

tags: `動態規劃(DP)` `記憶化搜尋(Memoization)` `填表法(Tabulation)`

題意

有 $n$ 個氣球，編號從 $0$ 到 $n - 1$ 。給定一個陣列 $nums$ 表示每個氣球上的數字。你的任務是戳破所有的氣球。

如果你戳破第 $i$ 個氣球，你會得到 $nums[i - 1] \times nums[i] \times nums[i + 1]$ 的硬幣。如果 $i - 1$ 或 $i + 1$ 超出陣列的範圍，那麼就把它們當作有一個寫著 $1$ 的氣球。

返回通過戳破氣球可以收集到的最多硬幣數量。

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

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

由於按照順序戳氣球需要維護氣球的狀態，所以我們可以倒序戳氣球，這樣就不需要維護氣球的狀態。假設在範圍 $[l, r]$ 中，最後一個戳破的氣球是第 $i$ 個氣球，那麼我們可以將問題分成兩個子問題：

戳破第 $i$ 個氣球左邊的所有氣球，即問題變成戳破 $[l, i]$ 中的氣球
戳破第 $i$ 個氣球右邊的所有氣球，即問題變成戳破 $[i, r]$ 中的氣球

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

$f(l, r) = \max\limits_{l < i < r} \{f(l, i) + f(i, r) + \text{nums}[l] \times \text{nums}[i] \times \text{nums}[r]\}$

因此可以用動態規劃(DP) 的方式來解決問題。

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

得到轉移式後，我們可以使用記憶化搜索的方式來解決問題。

比較直覺的方式是用遞迴的方式來解決問題，但是這樣會有大量的重複計算，所以我們需要使用記憶化搜尋(Memoization) ，將計算過的結果存起來，這樣就可以避免重複計算。在 Python 中可以使用 functools 模組中的 @cache 來進行記憶化搜索，而在 C++ 中需要使用一個二維陣列來存儲計算結果。

再來考慮邊界情況，當 $r - l \leq 1$ 時，表示只剩下一個或沒有氣球，此時就不需要戳氣球，所以返回 $0$ 。

寫出遞迴函數後，呼叫 $\rm{dfs}(0, n + 1)$ 即可得到答案。

複雜度分析

時間複雜度： $\mathcal{O}(n^3)$ ，總共有 $n^2$ 個子問題，每個子問題需要 $O(n)$ 的時間來計算。
空間複雜度： $\mathcal{O}(n^2)$ 。

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):
                cur = nums[left] * nums[i] * nums[right]
                cur += dfs(left, i) + dfs(i, right)
                res = max(res, cur)
            return res

        return dfs(0, n + 1)

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

方法二：填表法(Tabulation) / Bottom-up DP

類似的，我們也可以使用填表法(Tabulation) 的方式來解決問題，使用一個二維陣列 $dp$ 來存儲計算結果，其中 $dp[l][r]$ 表示戳破 $[l, r]$ 中的氣球所能獲得的最多硬幣數量。

再來考慮如何開始填表，由於 $dp[l][r]$ 依賴於 $dp[l][i]$ 和 $dp[i][r]$ ，所以我們可以從長度為 $3$ 的子問題開始填表，然後逐步增加子問題的長度，直到填滿整個表。

對於每個長度 $ln$ 的子問題，可以枚舉可能的左端點 $l$ ，然後計算出右端點 $r$ ，再枚舉可能的中間點 $m$ ，透過這些中間點 $m$ 來計算出 $dp[l][r]$ 。

完成填表後，答案就是 $dp[0][n + 1]$ 。

複雜度分析

時間複雜度： $\mathcal{O}(n^3)$ ，總共有 $n^2$ 個子問題，每個子問題需要 $O(n)$ 的時間來計算。
空間複雜度： $\mathcal{O}(n^2)$ 。

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        n = len(nums)
        nums = [1] + nums + [1]
        dp = [[0] * (n + 2) for _ in range(n + 2)]
        for ln in range(3, n + 3):  # length of subarray
            for l in range(n + 3 - ln):
                r = l + ln - 1
                for m in range(l + 1, r):
                    dp[l][r] = max(
                        dp[l][r],
                        dp[l][m] + dp[m][r] + nums[l] * nums[m] * nums[r])
        return dp[0][n + 1]

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 ln = 3; ln <= n + 2; ln++) {  // length of subarray
            for (int left = 0; left <= n + 2 - ln; left++) {
                int right = left + ln - 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];
    }
};