Interval DP區間 DP

01為什麼需要它

看到這些關鍵字就想到它：一段連續的東西、合併相鄰的兩段、最後一步切在哪裡、括號化、戳氣球、回文、三角剖分、dp[i][j] 看一個區間、依區間長度由短到長。

02核心概念

區間 DP 的狀態是一段連續的區間：dp[i][j] 是只考慮第 i 到第 j 個元素時的最佳答案。它適用於「整段的答案，可以拆成左右兩段的答案再合起來」的問題，而拆法就是枚舉分割點 k：dp[i][j] = best over k of (dp[i][k] ⊕ dp[k+1][j] + 合併這兩段的成本)。長度為 1 的區間通常是 base case，答案在 dp[0][n−1]。

關鍵是替每個區間挑一個讓左右兩邊互不影響的「決定」。以戳氣球為例，戳破一顆氣球得到「左鄰 × 自己 × 右鄰」分，鄰居會隨著戳破的順序改變。若枚舉「第一顆戳哪一顆」，戳完之後左右兩邊的氣球變成彼此的鄰居，子問題不獨立；改成枚舉「最後戳哪一顆 k」，在 (i, j) 裡 k 之前被戳破的都在它左邊或右邊，戳 k 的時候它的鄰居一定正好是 i 和 j，左右兩段完全獨立：dp[i][j] = max(dp[i][k] + dp[k][j] + a[i]·a[k]·a[j])。每一種戳法都有唯一的「最後一顆」，所以枚舉 k 不會漏掉任何方案。

填表順序很重要：dp[i][j] 用到的都是比它短的區間，所以外層迴圈跑區間長度、由短到長，內層枚舉起點 i；另一種寫法是 i 由大到小、j 由小到大。狀態有 O(n²) 個、每個枚舉 O(n) 個分割點，總共 O(n³) 時間、O(n²) 空間，大約 n ≤ 500 時可行。部分問題（例如最佳二元搜尋樹、滿足四邊形不等式的合併）可以用 Knuth 優化限制 k 的範圍，降到 O(n²)。

常見的坑：用「i 從小到大、j 從小到大」的雙迴圈直接填，dp[k+1][j] 還沒算就被拿去用；區間的開閉搞混，戳氣球用開區間 (i, j) 並在兩端補 1，矩陣鏈乘用閉區間 [i, j]，兩種寫法的邊界和 k 的範圍都不同；忘了合併成本要看整段，例如相鄰合併的成本是區間總和，要先建前綴和才能 O(1) 取得。和其他課程的關係：任兩堆都能合併時，貪婪的 Huffman Coding 就是最佳解，限制只能合併相鄰的，才需要區間 DP；最長回文子序列也可以看成字串和自己反轉的 LCS，但直接用區間狀態寫更自然，而且記憶化的遞迴版本和表格版是同一回事。

03演算法步驟

1. 1定義 dp[i][j] 為區間的最佳答案，決定用開區間還是閉區間，需要時在兩端補上哨兵（戳氣球補 1）。
2. 2填好 base case：長度 1（閉區間）或相鄰兩端之間沒有元素（開區間）的區間。
3. 3外層 length 由小到大，內層枚舉起點 i，算出 j。
4. 4枚舉分割點或「最後一步」k，dp[i][j] = best(dp[i][k] ⊕ dp[k+1][j] + 合併成本)；要還原方案就記下最佳的 k。區間總和這類成本先用前綴和備好。
5. 5答案在 dp[0][n−1]，沿著記下的 k 遞迴，就能還原括號方式或操作順序。

04互動示範

戳氣球 nums = [3, 1, 5, 8]，兩端補 1 變成 [1, 3, 1, 5, 8, 1]。表格裡的 dp[i][j] 是「把 i 和 j 之間的氣球全部戳破」的最大分數，依區間長度由短到長填。每一步假設某顆氣球 k 是這個區間裡最後被戳破的：上方的氣球列中藍色是 k，黃色是區間兩端，也就是戳 k 時的左右鄰居，灰色是在它之前已經被子問題戳掉的；表格裡藍色是正在填的格子，黃色是它用到的兩個子區間，格子右下角的小字記下選中的 k。最後 dp[0][5] = 167。

05程式碼

Python 放戳氣球、會還原括號方式的矩陣鏈乘，以及用記憶化遞迴寫的最長回文子序列，對照同一個區間狀態的兩種寫法。C++ 放戳氣球與「相鄰石堆合併」：後者的合併成本是整段總和，示範怎麼用前綴和在 O(1) 取得。

from functools import lru_cache


def max_coins(nums):
    """Burst Balloons：兩端補 1，dp[i][j] = 把開區間 (i, j) 內的氣球全部戳破的最大分數"""
    a = [1] + nums + [1]
    n = len(a)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n):                    # 區間長度由短到長，用到的子區間一定先算好
        for i in range(n - length):
            j = i + length
            dp[i][j] = max(dp[i][k] + dp[k][j] + a[i] * a[k] * a[j]   # k 是最後戳破的那顆
                           for k in range(i + 1, j))
    return dp[0][n - 1]


def matrix_chain(dims):
    """第 i 個矩陣是 dims[i-1] × dims[i]。回傳 (最少純量乘法次數, 最佳括號方式)"""
    n = len(dims) - 1
    cost = [[0] * (n + 1) for _ in range(n + 1)]
    split = [[0] * (n + 1) for _ in range(n + 1)]
    for length in range(2, n + 1):
        for i in range(1, n - length + 2):
            j = i + length - 1
            cost[i][j] = float("inf")
            for k in range(i, j):                 # 最後一次乘法把 A_i..A_k 和 A_k+1..A_j 接起來
                c = cost[i][k] + cost[k + 1][j] + dims[i - 1] * dims[k] * dims[j]
                if c < cost[i][j]:
                    cost[i][j], split[i][j] = c, k

    def paren(i, j):                              # 沿著記下的分割點還原括號
        k = split[i][j]
        return f"A{i}" if i == j else f"({paren(i, k)}{paren(k + 1, j)})"

    return cost[1][n], paren(1, n)


def longest_palindrome_subseq(s):
    """同樣的區間狀態寫成記憶化：參數就是區間的兩端"""
    @lru_cache(maxsize=None)
    def go(i, j):
        if i > j:
            return 0
        if i == j:
            return 1
        if s[i] == s[j]:
            return go(i + 1, j - 1) + 2           # 兩端相同，都收進回文
        return max(go(i + 1, j), go(i, j - 1))    # 否則丟掉其中一端
    return go(0, len(s) - 1)


if __name__ == "__main__":
    print(max_coins([3, 1, 5, 8]))                # 167（和互動示範相同）
    print(matrix_chain([10, 30, 5, 60]))          # (4500, '((A1A2)A3)')，另一種括號要 27000
    print(longest_palindrome_subseq("character")) # 5（例如 carac）

06練習題

• LeetCode 516Longest Palindromic Subsequence（兩端相同就收進去）Medium
• LeetCode 877Stone Game（區間上的兩人博弈）Medium
• LeetCode 1039Minimum Score Triangulation of Polygon（枚舉和兩端點組成三角形的頂點）Medium
• LeetCode 312Burst Balloons（枚舉最後戳的那一顆）Hard
• LeetCode 1547Minimum Cost to Cut a Stick（切點排序後就是區間 DP）Hard
• LeetCode 1000Minimum Cost to Merge Stones（每次合併 K 堆，狀態多一維）Hard