(Day 19) 動態規劃 (Dynamic Programming)

動態規劃 (Dynamic Programming; DP) 是一種將複雜問題分解為較小子問題，並儲存子問題解以避免重複計算的演算法設計方法。它常用於具有「重疊子問題」和「最優子結構」性質的問題

基本思想

動態規劃的核心思想是: 將原問題拆解成多個子問題，先解決並記錄子問題的解，當需要時直接查詢，從而提升效率。這種方法通常用於遞迴解法會產生大量重複計算的情況

適用條件

• 重疊子問題 (Overlapping Subproblems): 題可以分解為重複出現的子問題
• 最優子結構 (Optimal Substructure): 問題的最優解可以由子問題的最優解組合而成

基本步驟

1. 定義狀態: 找出如何用一組變數描述子問題
2. 狀態轉移方程: 找出子問題之間的遞推關係 (即狀態如何由更小的狀態推導而來)
3. 初始化: 設定最基本的子問題解 (通常是最小規模的情況)
4. 計算順序: 決定計算子問題的順序，通常是自底向上 (迴圈) 或自頂向下 (遞迴+記憶化)
5. 輸出答案: 根據需求輸出最終解

經典範例

• 費波那契數列 (Fibonacci Sequence): $F(n) = F(n-1) + F(n-2)$，用陣列儲存已計算的值
• 最短路徑問題 (Shortest Path): 如 Floyd-Warshall 演算法
• 背包問題 (Knapsack Problem): 給定物品重量和價值，求在容量限制下的最大總價值
• 最長公共子序列 (Longest Common Subsequence, LCS): 求兩個序列的最長公共子序列長度

優點

• 大幅減少重複計算，提高效率
• 適合解決最優化問題

缺點

• 需要額外的空間儲存子問題解
• 狀態設計和轉移方程推導有時較困難

舉例說明

費波那契數列

• 無使用動態規劃 (單純 Divide and Conquer)

  package io.twcch;
  
  import java.util.Scanner;
  
  public class Demo {
  
      public static long fibonacci(int index) {
          if (index == 0) {return 0;}
          if (index == 1) {return 1;}
  
          return fibonacci(index - 1) + fibonacci(index - 2);
      }
  
      public static void main(String[] args) {
          Scanner input = new Scanner(System.in);
          System.out.print("Enter an index for a Fibonacci number: ");
          int index = input.nextInt();
  
          System.out.print("The Fibonacci number at index " + index + " is " + fibonacci(index));
      }
  
  }
  

• 使用動態規劃

  package io.twcch;
  
  import java.util.HashMap;
  import java.util.Map;
  import java.util.Scanner;
  
  public class Demo {
  
      private static Map<Integer, Long> map = new HashMap<>();
  
      public static long fibonacci(int index) {
          if (map.containsKey(index)) {return map.get(index);}
  
          if (index == 0) {return 0;}
          if (index == 1) {return 1;}
  
          long result = fibonacci(index - 1) + fibonacci(index - 2);
  
          map.put(index, result);
  
          return result;
      }
  
      public static void main(String[] args) {
          Scanner input = new Scanner(System.in);
          System.out.print("Enter an index for a Fibonacci number: ");
          int index = input.nextInt();
  
          System.out.print("The Fibonacci number at index " + index + " is " + fibonacci(index));
      }
  
  }
  

結論

動態規劃是一種高效解決具有重疊子問題和最優子結構問題的強大工具。掌握動態規劃的思想和技巧，對於解決各類複雜演算法問題非常重要

備註

• 同步發表於 iThome 鐵人賽 2025 - 快速掌握資料結構與演算法