動態規劃 (Dynamic Programming)

將複雜問題分解為子問題的演算法策略

基本概念與條件

動態規劃適用於具備以下兩個性質的問題：

暴力遞迴為 O(2ⁿ)，動態規劃可優化至 O(n)。

def fibonacci_dp(n): 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]

自頂向下（記憶化）：遞迴 + 快取，只計算需要的子問題。

自底向上（表格法）：迭代填表，計算所有子問題，無遞迴開銷。

0/1 背包問題：在容量限制下選擇物品最大化價值。

最長公共子序列 (LCS)：找出兩個序列中最長的共同子序列。

最長遞增子序列 (LIS)：找出序列中最長的遞增子序列。

矩陣鏈乘積：找出最優的矩陣相乘順序。