掌握動態規劃（Dynamic Programming）的解題技巧

作者:
20241024192006 45

1. 什麼是動態規劃（Dynamic Programming）

定義與背景

動態規劃（Dynamic Programming，簡稱DP）是一種用於解決最優化問題的算法設計技術。它通常用於那些具有重疊子問題和最優子結構性質的問題。動態規劃的基本思想是將一個問題分解為多個子問題，然後將這些子問題的解存儲起來，以避免重複計算，從而提高效率。

歷史與應用

動態規劃的概念最早由美國數學家理查德·貝爾曼（Richard Bellman）於1950年代提出。隨著計算機科學的發展，動態規劃被廣泛應用於各個領域，如計算機科學中的算法設計、經濟學中的資源分配問題、工程學中的最優設計問題等。

這些應用範疇的共同特點是，它們通常涉及到選擇最佳方案來解決特定問題，例如在給定的限制下最大化利潤或最小化成本。

2. 動態規劃的基本概念

重疊子問題

重疊子問題是指在解決一個問題的過程中，會發現許多子問題被重複計算。在動態規劃中，我們會儲存這些子問題的結果，以便在需要時快速查詢，避免重複計算。

例子：斐波那契數列

斐波那契數列是最簡單的動態規劃例子之一。數列的定義為：

  • F(0) = 0
  • F(1) = 1
  • F(n) = F(n-1) + F(n-2) (n >= 2)

使用遞歸計算斐波那契數列時，會出現大量重複計算。例如，計算 F(5) 時需要計算 F(4) 和 F(3)，而 F(4) 又會計算 F(3) 和 F(2)，這樣就會導致 F(3) 被計算多次。

最優子結構

最優子結構是指問題的最優解可以由其子問題的最優解組成。這意味著，如果我們能找到子問題的最佳解，則可以利用這些解來構建整體問題的最佳解。

例子：背包問題

在 0-1 背包問題中，給定一組物品，每個物品有自己的價值和重量，我們需要在不超過背包容量的情況下，選擇物品使得總價值最大。這個問題具有最優子結構性質，因為選擇某個物品的最佳解可以基於已選擇物品的最佳解來決定。

3. 動態規劃的解題步驟

問題分解

動態規劃的第一步是將複雜問題分解為更小的子問題。這通常可以通過遞歸來描述問題的解法。

例子：計算斐波那契數列

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(5))  # 輸出 5

狀態定義

狀態定義是動態規劃中非常重要的一步。這需要我們明確定義每個子問題的狀態，以及如何從這些狀態轉移到下一個狀態。

例子：斐波那契數列的狀態轉移

在斐波那契數列中，我們可以定義狀態 F(n) 為第 n 個斐波那契數。狀態轉移方程為：

  • F(n) = F(n-1) + F(n-2)

邊界條件

在設計動態規劃算法時，設置基本情況的邊界條件是至關重要的。這些邊界條件可以幫助我們處理初始狀態。

例子：斐波那契數列的邊界條件

在上面的例子中，我們已經定義了 F(0) = 0 和 F(1) = 1 作為邊界條件。

4. 動態規劃的實現方法

自頂向下（Top-Down）

自頂向下的方法通常使用遞歸與記憶化搜索（Memoization）技術。這種方法的優點是直觀且易於實現，但可能會有堆疊溢出的風險。

例子：斐波那契數列的自頂向下實現

def fibonacci_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
    return memo[n]

print(fibonacci_memo(5))  # 輸出 5

自底向上（Bottom-Up）

自底向上的方法使用迴圈和表格填充的方法。這種方法通常更有效，因為它不會面臨堆疊溢出的問題，但在某些情況下實現較為複雜。

例子：斐波那契數列的自底向上實現

def fibonacci_bottom_up(n):
    if n <= 1:
        return n
    fib = [0] * (n + 1)
    fib[1] = 1
    for i in range(2, n + 1):
        fib[i] = fib[i-1] + fib[i-2]
    return fib[n]

print(fibonacci_bottom_up(5))  # 輸出 5

5. 常見的動態規劃問題

斐波那契數列

斐波那契數列的動態規劃解法已在前面介紹過。除了上述兩種方法，還可以進一步優化空間複雜度。

背包問題

0-1 背包問題

在 0-1 背包問題中，給定一組物品，每個物品有自己的價值和重量，背包有一定的容量，我們需要在不超過背包容量的情況下，選擇物品使得總價值最大。

動態規劃解法：

def knapsack(weights, values, capacity):
    n = len(values)
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
            else:
                dp[i][w] = dp[i - 1][w]

    return dp[n][capacity]

weights = [1, 2, 3]
values = [6, 10, 12]
capacity = 5
print(knapsack(weights, values, capacity))  # 輸出 22

最長公共子序列

最長公共子序列問題是從兩個序列中找出其公共子序列的最長長度。

動態規劃解法：

def lcs(X, Y):
    m = len(X)
    n = len(Y)
    dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]

X = "AGGTAB"
Y = "GXTXAYB"
print(lcs(X, Y))  # 輸出 4

6. 動態規劃的技巧與最佳實踐

狀態壓縮

狀態壓縮是一種減少空間複雜度的技術。在某些動態規劃問題中，我們只需要保留最近的幾個狀態，而不需要保留所有的狀態。

例子：斐波那契數列的狀態壓縮

def fibonacci_optimized(n):
    if n <= 1:
        return n
    prev1, prev2 = 0, 1
    for _ in range(2, n + 1):
        curr = prev1 + prev2
        prev1, prev2 = prev2, curr
    return prev2

print(fibonacci_optimized(5))  # 輸出 5

識別問題的特徵

在實際應用中，快速識別一個問題是否適合使用動態規劃的方法是非常重要的。以下是一些常見的特徵：

  • 問題可以被分解為子問題。
  • 子問題的解可以重複使用。
  • 子問題的解可以組合成整體問題的解。

實踐中的建議

  • 練習題資源與平台推薦：LeetCode、HackerRank、Codeforces等平台有許多動態規劃的練習題。
  • 常見陷阱：忽視邊界條件、未能正確識別子問題的重複性等。

動態規劃是一個強大的工具，透過不斷的練習與實踐，能夠在解決複雜問題時發揮巨大的作用。希望這篇文章能幫助你更深入地理解動態規劃的基本概念與實現技巧。

關於作者

Carger
Carger
我是Oscar (卡哥)，前Yahoo Lead Engineer、高智商同好組織Mensa會員，超過十年的工作經驗，服務過Yahoo關鍵字廣告業務部門、電子商務及搜尋部門，喜歡彈吉他玩音樂，也喜歡投資美股、虛擬貨幣，樂於與人分享交流！