03.2-動態規劃法

動態規劃法（Dynamic Programming, DP）是一種用於解決複雜問題的算法技術。這些問題通常可以被分解為更小的子問題，並且子問題之間有重複的計算。動態規劃通過將這些子問題的解結果存儲起來，避免重複計算，從而提高效率。動態規劃適用於具有重疊子問題和最優子結構的問題。

1. 動態規劃的基本概念#

重疊子問題：問題的解可以通過多次解決相同的子問題來得到。這些子問題在求解過程中會重複出現，這是動態規劃的關鍵特點。
最優子結構：問題的最優解可以由其子問題的最優解組合而成。也就是說，問題的全局最優解包含了子問題的最優解。

2. 動態規劃的解題步驟#

動態規劃的解題過程一般包括以下步驟：

定義狀態：首先，將問題拆解為一系列子問題，定義每個子問題的狀態表示。通常，這些狀態是一組變量的值。
確定遞推公式：根據問題的結構，找到子問題之間的關係。這通常是通過最優子結構的特性來實現的，確定如何利用已經解決的子問題來構建更大範圍的解。
初始化：確定邊界條件，也就是最小的子問題的解。
計算順序：根據遞推公式的結構，按某種順序計算子問題的解，直到求出最終問題的解。
回溯（若需要）：如果問題需要構建解的具體步驟，可以從最終的解回溯到初始狀態。

3. 動態規劃的兩種形式#

自頂向下（Top-Down）：這種方法通常使用遞歸來解決問題，並利用備忘錄（Memoization）來存儲已經計算過的結果，避免重複計算。這種方法常用於解決具有重疊子問題的問題。
自底向上（Bottom-Up）：這種方法從最小的子問題開始，逐步構建解的過程。它通常使用迭代方式，從基礎情況開始，逐步向問題的最終解推進。

4. 動態規劃法的例子#

4.1 斐波那契數列#

斐波那契數列是一個經典的動態規劃問題，其中每個數字是前兩個數字的和。這個問題具有重疊子問題的特性，因為同樣的子問題會被多次計算。

斐波那契數列的遞推公式： [ F(n) = F(n-1) + F(n-2) ] 其中， \(F(0) = 0\) 和 \(F(1) = 1\) 。

自頂向下（帶備忘錄）：#

def fibonacci_top_down(n, memo={}):
    if n in memo:
        return memo[n]
    if n == 0:
        return 0
    elif n == 1:
        return 1
    memo[n] = fibonacci_top_down(n-1, memo) + fibonacci_top_down(n-2, memo)
    return memo[n]

print(fibonacci_top_down(10))  # 輸出：55

自底向上：#

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

print(fibonacci_bottom_up(10))  # 輸出：55

4.2 背包問題#

背包問題是另一個經典的動態規劃問題，目標是從一組物品中選擇若干個物品，使得它們的總價值最大，並且總重量不超過背包的最大容量。這個問題具有最優子結構的特性。

問題定義： - 給定 \(n\) 個物品，每個物品有一個重量和價值。 - 給定背包的最大承重 \(W\) 。 - 求在背包容量不超過 \(W\) 的情況下，可以獲得的最大價值。

遞推公式： - \(dp[i][w]\) 表示前 \(i\) 個物品，總重量不超過 \(w\) 時的最大價值。 - 若不選擇第 \(i\) 個物品，則 \(dp[i][w] = dp[i-1][w]\) 。 - 若選擇第 \(i\) 個物品，則 \(dp[i][w] = dp[i-1][w-w[i]] + v[i]\) ，其中 \(w[i]\) 是第 \(i\) 個物品的重量， \(v[i]\) 是第 \(i\) 個物品的價值。

代碼實現：#

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

    for i in range(1, n + 1):
        for w in range(1, W + 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][W]

weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
W = 5
print(knapsack(weights, values, W))  # 輸出：7

5. 動態規劃法的優缺點#

優點：#

減少重複計算：動態規劃有效地避免了計算過程中的重複工作，通過存儲已解決的子問題結果來提高效率。
適用於複雜問題：對於具有最優子結構和重疊子問題的問題，動態規劃能夠提供高效的解法。
能夠求解最優解：動態規劃通常能找到問題的最優解。

缺點：#

空間複雜度高：由於需要存儲子問題的解，動態規劃的空間開銷可能比較大，尤其是對於大規模問題。
難以理解：動態規劃問題的建模和遞推公式的設計可能比較難，特別是對於新手而言。

6. 總結#

動態規劃是一種強大的算法技術，能夠高效解決許多具有重疊子問題和最優子結構的問題。它在許多領域都有廣泛應用，從背包問題、最短路徑問題到股票買賣問題等。儘管動態規劃的實現可能比較複雜，但一旦掌握了其基本思想，它將成為解決複雜問題的強大工具。