漫談算法（二）：動態規劃核心思想與經典案例實戰

作者：劉子韜

動態規劃本質

Dynamic Programming 中的 Programming 指「表格法」，而非編程。核心：用表格保存子問題結果，避免遞歸重複計算。

與分治區別：分治子問題獨立，DP 子問題重疊。

兩大設計思路

1. 遞歸 + 備忘錄：先寫遞歸，再用表格緩存中間結果（《算法導論》主推）
2. 窮盡搜索 + 剪枝：構造枚舉樹，葉子為候選解，剪枝規則修剪搜索空間（作者老師 Kirk 發明，參考論文《How to design dynamic programming algorithms sans recursion》）

經典案例 1：鋼條切割問題

問題

長度 n 米鋼條，價格表 p[i]（長度 i 價格）。求切割方案最大化收益。

遞歸思路

第一刀切在 i 處：收益 = p[i] + Cut(n-i)。遍歷 i 取最大值。

Cut(P, n):
    if n == 0: return 0
    q = -∞
    for i = 1 to n:
        q = max(q, P[i] + Cut(P, n-i))
    return q

DP 表格法

Cut(P, n):
    r[0] = 0
    for i = 1 to n:
        q = -∞
        for j = 1 to i:
            q = max(q, P[j] + r[i-j])
        r[i] = q
    return r[n]

經典案例 2：最長公共子序列 (LCS)

問題

序列 X (長 n)、Y (長 m)，求最長公共子序列長度。

遞歸定義

設指針 i, j 分別指向 X, Y 末尾：

• X[i] == Y[j]：LCS(i,j) = LCS(i-1,j-1) + 1
• X[i] != Y[j]：LCS(i,j) = max(LCS(i-1,j), LCS(i,j-1))
• i=0 或 j=0：return 0

DP 表格構建

// 初始化：第 0 行/列 = 0
for i = 1 to m:
    for j = 1 to n:
        if X[i] == Y[j]:
            LCS[i,j] = LCS[i-1,j-1] + 1
        else:
            LCS[i,j] = max(LCS[i,j-1], LCS[i-1,j])

經典案例 3：矩陣鏈乘法優化

問題

矩陣鏈 A₁...Aₙ，Aᵢ 為 P_i-1×P_i。求乘法順序使標量乘法次數最小。

遞歸思路

在 k 處分割：m[i,j] = min_{i≤k (m[i,k] + m[k+1,j] + Pi-1PkPj)}

基例：i==j 時 m[i,j]=0

DP 實現

// 初始化：對角線 = 0
for l = 2 to n:          // 鏈長
    for i = 1 to n-l+1:
        j = i + l - 1
        m[i,j] = ∞
        for k = i to j-1:
            q = m[i,k] + m[k+1,j] + P[i-1]*P[k]*P[j]
            if q < m[i,j]: m[i,j] = q

進階案例：最長回文子序列 & 最長遞增子序列 (LIS)

窮盡搜索 + 剪枝思想演示（LIS）

輸入 X₁...Xₙ，構造枚舉樹：每層決定「選/不選」當前元素。

剪枝規則設計

1. 可行性剪枝：當前序列非遞增 → 剪枝
2. 最優性剪枝：當前長度 + 剩餘元素數 ≤ 已找到最長長度 → 剪枝
3. 支配關係剪枝：同層節點，若節點 A 末尾元素 ≤ 節點 B 末尾元素，且 A 長度 ≥ B 長度 → B 被 A 支配，剪枝 B

LIS 的 O(n log n) 貪心 + 二分優化

維護數組 tail[len] 存儲長度為 len 的遞增子序列最小末尾值。遍歷輸入，二分查找插入位置更新 tail。最終 tail 長度即 LIS 長度。

總結

動態規劃核心三要素：重疊子問題、最優子結構、無後效性。兩大設計路徑各有千秋：遞歸+備忘錄直觀易寫；窮盡搜索+剪枝揭示問題結構，適合複雜約束場景。經典案例展示了從 1D 到 2D 表格的構建模式，掌握「狀態定義 → 轉移方程 → 初始化 → 計算順序」四步法，DP 諸題迎刃而解。