題目描述：有 n 個氣球，第 i 個氣球上標有數字 nums[i]。每次戳破第 i 個氣球可以獲得 nums[i-1] * nums[i] * nums[i+1] 枚金幣（邊界外視為 1）。請求戳破所有氣球能獲得的最大金幣數。
解題思路：
這題的關鍵思維轉換：不要想「第一個戳哪個」，而是想「最後一個戳哪個」。
區間 DP 設計：
nums 兩端加上哨兵 1，形成新陣列 arr（長度 n+2）dp[l][r] = 戳破所有嚴格在 (l, r) 之間的氣球能獲得的最大金幣l 和 r 對應的氣球不被戳破，作為「虛擬邊界」狀態轉移：
枚舉 k（l < k < r），k 是此區間中最後一個被戳破的氣球：
dp[l][r] = max over k of:
dp[l][k] + arr[l]*arr[k]*arr[r] + dp[k][r]
dp[l][k]：先戳破 (l,k) 之間的所有氣球arr[l]*arr[k]*arr[r]：最後戳破 k，此時左鄰為 l，右鄰為 rdp[k][r]：先戳破 (k,r) 之間的所有氣球填表順序：按區間長度由小到大遍歷（長度 2 開始，即 r - l >= 2）。
時間複雜度：O(n³) — 三層迴圈：外層枚舉區間長度 O(n)、中層枚舉左端點 O(n)、內層枚舉最後戳破的氣球 k O(n)，共 O(n³)。
空間複雜度：O(n²) — 需要 (n+2)×(n+2) 的二維 DP 表格來儲存所有區間的最優解。
1. Build arr = [1] + nums + [1] (add sentinel values, N = n+2)
2. Initialize dp[N][N] = all zeros
3. For len from 2 to N-1 (interval length):
For l from 0 to N-1-len:
Set r = l + len
For k from l+1 to r-1 (k is the LAST balloon burst in open interval (l,r)):
coins = dp[l][k] + arr[l]*arr[k]*arr[r] + dp[k][r]
dp[l][r] = max(dp[l][r], coins)
4. Return dp[0][N-1]記憶化遞迴 O(n³)：等價於迭代 DP，用 solve(l, r) 遞迴計算，memo[l][r] 快取結果。實作上從 solve(0, N-1) 開始，思路與迭代版相同，但對初學者可能更直觀；缺點是遞迴呼叫有額外堆疊開銷。
暴力回溯 O(n! 或指數級)：直接枚舉所有戳氣球的排列順序，模擬每種順序的得分並取最大值。雖然正確，但 n 稍大（如 n=20）即超時，僅適合理解問題用，無法通過本題。