動態規劃（Dynamic Programming）是解決復雜優化問題的核心技術，也是算法領域的明珠。本文將深入探討Python實現動態規劃的全方位技術，涵蓋基礎概念、經典問題、優化技巧和實際工程應用，帶您掌握這一強大工具的精髓。

一、動態規劃的本質：最優決策的藝術

動態規劃不是簡單的編程技巧，而是一種系統化的決策方法論。其核心思想是理查德·貝爾曼提出的"最優性原理"：一個多階段決策過程的最優策略具有這樣的性質，即無論初始狀態和初始決策如何，其余決策必須構成最優策略。

動態規劃三大特征：

1. 重疊子問題：問題可分解為重復計算的子問題

2. 最優子結構：問題最優解包含子問題最優解

3. 無后效性：當前決策不影響先前狀態

# 斐波那契數列的遞歸與DP對比
def fib_recursive(n):if n <= 1: return nreturn fib_recursive(n-1) + fib_recursive(n-2)  # 指數級復雜度def fib_dp(n):if n == 0: return 0dp = [0] * (n+1)dp[1] = 1for i in range(2, n+1):dp[i] = dp[i-1] + dp[i-2]  # 線性復雜度return dp[n]# 測試：n=40
%timeit fib_recursive(40)  # 約10秒
%timeit fib_dp(40)        # 約0.5微秒

二、動態規劃四步解題框架

步驟1：定義狀態

• 明確dp數組含義

• 確定狀態變量和維度

步驟2：建立狀態轉移方程

• 找到狀態間遞推關系

• 數學化表示最優子結構

步驟3：初始化邊界條件

• 設置初始狀態值

• 處理特殊情況

步驟4：確定計算順序

• 自底向上或自頂向下

• 確保無后效性

def coin_change(coins, amount):"""零錢兌換問題：最少硬幣數"""# 步驟1：定義狀態 - dp[i]表示金額i的最小硬幣數dp = [float('inf')] * (amount+1)# 步驟2：初始化邊界 - 金額0需要0枚硬幣dp[0] = 0# 步驟3：狀態轉移for coin in coins:for i in range(coin, amount+1):dp[i] = min(dp[i], dp[i-coin] + 1)# 步驟4：返回結果return dp[amount] if dp[amount] != float('inf') else -1# 測試
print(coin_change([1, 2, 5], 11))  # 輸出：3 (5+5+1)

三、經典動態規劃問題精解

3.1 背包問題：組合優化的基石

0-1背包問題：

def knapsack_01(weights, values, capacity):n = len(weights)# dp[i][w] 前i個物品放入容量w的最大價值dp = [[0]*(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 = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8
print(knapsack_01(weights, values, capacity))  # 輸出：10 (物品2+4)

完全背包問題：

def knapsack_unbounded(weights, values, capacity):dp = [0] * (capacity+1)for w in range(1, capacity+1):for i in range(len(weights)):if weights[i] <= w:dp[w] = max(dp[w], dp[w-weights[i]] + values[i])return dp[capacity]# 測試
print(knapsack_unbounded(weights, values, capacity))  # 輸出：12 (物品1*4)

3.2 最長公共子序列（LCS）

def longest_common_subsequence(text1, text2):m, n = len(text1), len(text2)# dp[i][j] 表示text1[0:i]和text2[0:j]的LCS長度dp = [[0]*(n+1) for _ in range(m+1)]for i in range(1, m+1):for j in range(1, n+1):if text1[i-1] == text2[j-1]:dp[i][j] = dp[i-1][j-1] + 1else:dp[i][j] = max(dp[i-1][j], dp[i][j-1])# 回溯構造LCSlcs = []i, j = m, nwhile i > 0 and j > 0:if text1[i-1] == text2[j-1]:lcs.append(text1[i-1])i -= 1j -= 1elif dp[i-1][j] > dp[i][j-1]:i -= 1else:j -= 1return dp[m][n], ''.join(reversed(lcs))# 測試
text1 = "abcde"
text2 = "ace"
length, seq = longest_common_subsequence(text1, text2)
print(f"長度: {length}, 序列: {seq}")  # 長度: 3, 序列: "ace"

3.3 最短編輯距離

def min_edit_distance(word1, word2):m, n = len(word1), len(word2)dp = [[0]*(n+1) for _ in range(m+1)]# 初始化邊界for i in range(1, m+1):dp[i][0] = ifor j in range(1, n+1):dp[0][j] = j# 狀態轉移for i in range(1, m+1):for j in range(1, n+1):if word1[i-1] == word2[j-1]:dp[i][j] = dp[i-1][j-1]else:dp[i][j] = min(dp[i-1][j] + 1,    # 刪除dp[i][j-1] + 1,    # 插入dp[i-1][j-1] + 1   # 替換)return dp[m][n]# 測試
print(min_edit_distance("horse", "ros"))  # 輸出：3 (h->r, 刪o, 刪e)