動態規劃算法全面解析

動態規劃（Dynamic Programming，DP）是一種通過將復雜問題分解為重疊子問題，并利用子問題的解來高效解決原問題的算法思想。它與分治法類似，但更注重對重復子問題的優化，避免重復計算，從而大幅提升算法效率。

一、核心思想與基本概念

1. 重疊子問題（Overlapping Subproblems）
   問題可以分解為多次重復出現的子問題。例如斐波那契數列中，計算fib(n)時需要重復計算fib(n-1)和fib(n-2)。

2. 最優子結構（Optimal Substructure）
   問題的最優解包含子問題的最優解。例如最短路徑問題中，從A到C的最短路徑必然包含A到B的最短路徑（若B是路徑中的節點）。

3. 狀態轉移方程
   用數學公式定義子問題之間的關系，是動態規劃的核心。例如斐波那契數列的狀態轉移方程為：
   $$fib(n)=?\begin{array}{ll}0,& n=0\\ 1,& n=1\\ fib(n?1)+fib(n?2),& n>1\end{array}$$

二、動態規劃與其他算法的區別

算法類型	核心策略	重復子問題處理	典型案例
動態規劃	利用子問題解存儲與復用	存儲結果避免重復計算	背包問題、最長公共子序列
分治法	將問題分解為獨立子問題	不存儲子問題解	歸并排序、快速冪
貪心算法	每一步選擇局部最優解	不考慮子問題重疊	霍夫曼編碼、活動選擇問題

三、動態規劃的解題步驟

1. 定義狀態
   明確dp[i]表示什么，通常與問題的規模或階段相關。例如：

   • dp[i]：長度為i的序列的最優解
   • dp[i][j]：二維問題中第i行第j列的狀態

2. 推導狀態轉移方程
   找出dp[i]與dp[i-1]、dp[i-2]等子狀態的關系，例如：

   • 背包問題：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
   • 最長遞增子序列（LIS）：dp[i] = max(dp[j] + 1) ，其中j < i且nums[j] < nums[i]

3. 確定初始條件
   處理最小規模的子問題，例如：

   • dp[0] = 0（空序列的解）
   • dp[i][0] = 0（背包容量為0時無法裝物品）

4. 確定計算順序
   確保計算dp[i]時，其依賴的子狀態已被計算，通常采用自底向上（迭代）的方式。

5. 獲取最終結果
   根據問題要求，從狀態數組中提取答案（可能是dp[n]或max(dp[1..n])等）。

四、經典案例解析

1. 斐波那契數列（Fibonacci）

• 問題：計算第n個斐波那契數。
• 暴力遞歸：時間復雜度O(2^n)，存在大量重復計算。
• 動態規劃解法：

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

• 優化：只需存儲前兩個狀態，空間復雜度從O(n)降為O(1)：

  def fib_optimized(n):if n <= 1:return na, b = 0, 1for _ in range(2, n + 1):a, b = b, a + breturn b
  

2. 0-1背包問題（0-1 Knapsack）

• 問題：有n個物品，每個物品重量w[i]、價值v[i]，背包容量W，求能裝的最大價值。
• 狀態定義：dp[i][j]表示前i個物品放入容量為j的背包的最大價值。
• 狀態轉移：
  • 不選第i個物品：dp[i][j] = dp[i-1][j]
  • 選第i個物品（若j >= w[i]）：dp[i][j] = dp[i-1][j-w[i]] + v[i]
  • 最終：dp[i][j] = max(不選, 選)
• 代碼實現：

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

• 空間優化：使用一維數組，逆序更新（避免重復使用當前物品）：

  def knapsack_optimized(w, v, W):n = len(w)dp = [0] * (W + 1)for i in range(n):for j in range(W, w[i] - 1, -1):dp[j] = max(dp[j], dp[j - w[i]] + v[i])return dp[W]
  

3. 最長公共子序列（LCS）

• 問題：求兩個字符串A和B的最長公共子序列長度。
• 狀態定義：dp[i][j]表示A[0..i-1]和B[0..j-1]的LCS長度。
• 狀態轉移：
  • 若A[i-1] == B[j-1]：dp[i][j] = dp[i-1][j-1] + 1
  • 否則：dp[i][j] = max(dp[i-1][j], dp[i][j-1])
• 代碼示例：

  def lcs_length(text1, text2):m, n = len(text1), len(text2)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])return dp[m][n]
  

五、動態規劃的優化技巧

1. 空間壓縮

   • 一維DP：將二維狀態數組壓縮為一維（如0-1背包的優化）。
   • 滾動數組：僅保留與當前狀態相關的前幾個子狀態（如斐波那契數列）。

2. 狀態轉移優化

   • 利用數據結構（如平衡樹、單調隊列）加速狀態轉移。
   • 矩陣快速冪：將線性遞推關系轉化為矩陣乘法，適用于大規模數據。

3. 記憶化搜索（自頂向下）

   • 用遞歸+緩存的方式避免重復計算，適合子問題依賴關系復雜的場景。

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

六、動態規劃的應用場景

• 組合優化問題：背包問題、旅行商問題（TSP）、最短路徑。
• 字符串處理：編輯距離、最長回文子串、正則表達式匹配。
• 數學問題：硬幣找零、整數拆分、矩陣鏈乘法。
• 概率與統計：股票買賣最佳時機、骰子點數組合。
• 圖論問題：狀態壓縮DP（如哈密頓路徑）。

七、動態規劃與貪心的對比

• 動態規劃：考慮所有可能的子問題，確保全局最優，但時間復雜度較高。
• 貪心算法：每一步選局部最優，可能無法得到全局最優，但效率更高。
• 案例對比：
  • 活動選擇問題：貪心可直接選結束時間最早的活動，無需DP。
  • 背包問題：貪心（按單位重量價值選）無法得到最優解，必須用DP。

八、學習建議

1. 從基礎案例入手：先掌握斐波那契、背包、LCS等經典問題。
2. 多練習狀態定義：動態規劃的核心難點在于狀態轉移方程的推導。
3. 注意邊界條件：初始狀態的設定直接影響結果正確性。
4. 分析時間與空間復雜度：優化算法時需平衡兩者。
5. 參考解題模板：許多DP問題有固定的狀態設計模式（如區間DP、樹形DP）。

動態規劃是算法設計中最具挑戰性的思想之一，但通過大量練習和總結，能夠有效提升解決復雜問題的能力。