跳至主要内容

Dynamic Programming

動態規劃（Dynamic Programming，簡稱 DP）是一種 「把大問題拆成小問題，並把算過的答案記下來」 的技巧。

例如銀行帳戶初始餘額是 0，但每次都記錄上一次交易後的餘額，這樣就不用每次查看餘額都須從初始狀態開始算。

這種「用空間換取時間」的方法，可以讓原本要算很久的題目，在幾秒鐘內就解出來。

白話理解

想像數學考卷上有個好幾個題目組成的題組，某個問題的答案需要用到前面幾題的答案。

如果每次都重新計算，會浪費很多時間在算「早就算過的答案」。DP 的做法是準備一張小抄，算過的答案就先寫下來，下次遇到一樣的題目直接抄小抄，不用再重算一次。

核心兩大特徵​

如果一個問題可以用 DP 來解，它通常會符合以下兩個特色：

  • 重疊子問題（Overlapping Sub-problems）：大問題拆開後，會重複出現一模一樣的小問題
  • 最佳子結構（Optimal Substructure）：小問題的最佳答案，可以組合成大問題的最佳答案

範例​

費氏數列（Fibonacci）是解釋 DP 的經典例題，可參考 Leetcode 題目。

題目：費氏數列的規則是後面的數字等於前面兩個數字相加（1, 1, 2, 3, 5, 8...），算出第 n 個數字為多少。

Example 1:
Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Example 2:
Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

暴力解​

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)
  • Time Complexity: O(2^n)
  • Space Complexity: O(n)

如果是要算第 4 個數字，則會拆成：

                  fib(4)
                 /      \
           fib(3)        fib(2)
          /      \       /     \
      fib(2)   fib(1)  fib(1)  fib(0)
     /      \
 fib(1)   fib(0)

其中

  • fib(2) 被完整計算了 2 次。
  • fib(1) 被完整計算了 3 次。

重複計算都是額外消耗時間。

DP 解​

費氏數列的定義：後面的數字等於前面兩個數字相加 f(n) = f(n-1) + f(n-2)

滿足可用 DP 的特徵：

  • 重疊子問題（Overlapping Sub-problems）：大問題拆開後，會重複出現一模一樣的小問題
  • 最佳子結構（Optimal Substructure）：小問題的最佳答案，可以組合成大問題的最佳答案

因此，只需多加一個變數以儲存已經處理過的問題，之後再有需要即可直接存取。

def fib(n):
    if n <= 1:
        return n
    memo = [0, 1]  # 儲存計算過的內容

    for i in range(2, n + 1):
        memo.append(memo[i - 1] + memo[i - 2])

    return memo[n]
  • Time Complexity: O(n)　　
  • Space Complexity: O(n)

因為每個 fib(i) 只會被計算一次，之後都是直接從 memo 陣列裡讀取，不再重複計算，時間複雜度直接從指數等級的 O(2^n) 降到線性的 O(n)。

兩種實作方向：Top-Down 與 Bottom-Up​

DP 通常有兩種寫法，解決的問題一樣，但思考方向相反：

  • Top-Down（由上而下）：也就是「Memoization」，寫法上維持原本遞迴的樣子，只是多加一個 memo 來記錄算過的結果，遇到已經算過的直接回傳，不用重算。
  • Bottom-Up（由下而上）：也就是「Tabulation」，前面費氏數列的 DP 解就是這種寫法。直接從最小的子問題開始，用迴圈一步步往上算，最後算出目標答案，完全不使用遞迴。
# Top-Down（Memoization）版本的費氏數列
def fib(n, memo=None):
    if memo is None:
        memo = {}
    if n <= 1:
        return n
    if n in memo:
        return memo[n]  # 算過了，直接回傳

    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)  # 沒算過，算完順便存起來
    return memo[n]
比較項目Top-Down（Memoization）Bottom-Up（Tabulation）
寫法保留遞迴，額外加上 memo 快取改寫成迴圈，由小到大逐步計算
直覺度通常較貼近原始問題的定義，比較好想需要先想清楚「計算順序」，但沒有遞迴的額外負擔
空間消耗遞迴會佔用 Call Stack 空間（可參考 Recursion）通常只需要陣列或變數，沒有 Call Stack 的額外消耗
建議剛開始學 DP 時，可以先從這個方向下手，比較容易想通熟悉之後，可以練習把 Top-Down 的解法改寫成這種形式，訓練優化能力

適用情況​

除了費氏數列，以下這些經典題型都是用 DP 解決的：

  • 背包問題（Knapsack Problem）：在背包容量限制下，選擇物品使總價值最大化。
  • 最長共同子序列（Longest Common Subsequence）：比對兩個字串，找出最長且順序一致（不需連續）的共同片段。
  • 爬樓梯（Climbing Stairs）：每次可以爬 1 或 2 階，問爬到第 n 階有幾種走法（本質上和費氏數列是同一種遞迴關係）。
  • 編輯距離（Edit Distance）：計算把一個字串改成另一個字串，最少需要幾次新增、刪除或替換字元。

常見誤區​

  • 看到「重複子問題」就以為一定要用 DP：DP 還需要具備「最佳子結構」，也就是子問題的最佳解真的能組合成大問題的最佳解，兩個條件缺一不可，並非所有遞迴問題都適合套用 DP。
  • 忘記設定正確的初始值（Base Case）：Bottom-Up 寫法特別容易出錯在 memo 陣列最前面幾格的初始值，如果初始值設錯，後面所有依賴它計算出來的結果都會跟著錯。
  • Top-Down 忘記檢查快取，或是快取的 key 設計錯誤：如果狀態不只依賴一個變數（例如同時依賴「目前位置」和「剩餘容量」），memo 的 key 必須把所有會影響結果的變數都包含進去，只記錄其中一個變數會導致誤判「這個子問題已經算過」。
  • DP 和 Greedy 選錯邊：如果不確定「每一步選當下最好的」是否保證整體最優，建議先假設不保證，改用 DP 全部列出來比較，會比較保險，可參考 Greedy Algorithm 裡的比較。
最後於 更新