動態規劃例題用法介紹

本文將以動態規劃（Dynamic Programming, DP）例題為中心，深入闡述動態規劃的原理和應用。

一、最長公共子序列問題

最長公共子序列問題（Longest Common Subsequence, LCS）是一道經典的動態規劃問題。給定兩個字符串 s1 和 s2，找到它們之間最長的公共子序列（可以不連續）。

在解決這個問題時，我們可以使用二維數組 dp 來進行動態規劃。數組 dp 中的 dp[i][j] 表示 s1 的前 i 個字符和 s2 的前 j 個字符之間的最長公共子序列長度。下面是對應的 Python 代碼：

def longestCommonSubsequence(s1: str, s2: str) -> int:
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[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]

在這段代碼中，我們首先定義了兩個字符串 s1 和 s2 的長度 m 和 n。然後使用一個二維數組 dp 來存儲動態規劃的結果。接着我們進行兩層 for 循環，枚舉 s1 和 s2 的所有情況。對於每一個狀態 dp[i][j]，如果 s1[i-1] 等於 s2[j-1]，那麼當前位置的最長公共子序列長度就為 dp[i-1][j-1] + 1，否則就為 max(dp[i-1][j], dp[i][j-1])。最後，我們返回 dp[m][n] 的值即可。

二、0/1背包問題

0/1背包問題（0/1 Knapsack Problem）也是一道經典的動態規劃問題。給定一個背包容量和若干個物品，每個物品有兩個屬性：重量和價值。要求在不超過背包容量的情況下，選擇一些物品裝入背包，使得背包中物品的總價值最大。

我們同樣可以使用二維數組 dp 來進行動態規劃。數組 dp 中的 dp[i][j] 表示在前 i 個物品中，容量不超過 j 的情況下，選擇物品的最大價值。下面是對應的 Python 代碼：

def knapsack(w: List[int], v: List[int], c: int) -> int:
    n = len(w)
    dp = [[0] * (c + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, c + 1):
            if j < w[i - 1]:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1])
    return dp[n][c]

在這段代碼中，我們同樣定義了物品的重量 w、價值 v，以及背包的容量 c。然後使用一個二維數組 dp 來存儲動態規劃的結果。接着我們進行兩層 for 循環，枚舉前 i 個物品以及不同的容量情況。對於每一個狀態 dp[i][j]，如果當前物品的重量 w[i-1] 大於背包剩餘容量 j，那麼就不能選擇該物品，當前狀態的最大價值就等於上一個狀態 dp[i-1][j] 的價值。否則，我們需要選擇該物品，因此當前狀態的最大價值就等於 dp[i-1][j-w[i-1]] + v[i-1] 和 dp[i-1][j] 中的較大值。最後，我們返回 dp[n][c] 的值即可。

三、斐波那契數列問題

斐波那契數列（Fibonacci Sequence）也是一道常見的動態規劃問題。斐波那契數列中的第 n 項可以用以下遞歸公式表示：

F(n) = F(n-1) + F(n-2), F(0) = 0, F(1) = 1

但是這種遞歸過程效率較低，因為在遞歸中會有大量重複計算。我們可以使用一個數組來記錄已經計算好的中間值，以避免重複計算。下面是對應的 Python 代碼：

def fib(n: int) -> int:
    if n <= 1:
        return n
    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]

在這段代碼中，我們先判斷輸入的 n 是否小於等於 1，如果是的話直接返回 n。否則，我們定義一個數組 dp 來記錄已經計算好的中間值。數組 dp 中的 dp[i] 表示斐波那契數列中的第 i 項。接着，使用一個 for 循環進行動態規劃計算。在這個 for 循環中，每次都將 dp[i] 的值更新為 dp[i-1] 和 dp[i-2] 的和。最後，我們返回 dp[n] 的值即可。