[演算法] 動態規劃（Dynamic Programming, DP）

 動態規劃（Dynamic Programming, DP）是一種解決最優化問題（Optimization Problems）的算法設計技巧。它通過將問題分解成更小、更簡單的子問題（Subproblems）來解決原始問題，並且保存子問題的解以避免重複計算。動態規劃通常用於解決具有重疊子問題（Overlapping Subproblems）和最優子結構（Optimal Substructure）特點的問題。以下是動態規劃的基本步驟和一些例子：

1. **定義子問題 (Define Subproblems)**:

   - 將原始問題分解成更小、更簡單的子問題。

2. **建立遞推關係 (Establish Recurrence Relations)**:

   - 找出子問題之間的關係，以及如何由子問題的解得到原始問題的解。

3. **初始化基礎情況 (Initialize Base Cases)**:

   - 設定某些基本情況，使得動態規劃算法可以正確地開始。

4. **計算子問題的解並存儲 (Compute Subproblems and Store)**:

   - 自底向上（Bottom-up）或自頂向下（Top-down）的計算子問題的解，並將結果存儲在表中（Table）以供後續使用。

5. **構建原始問題的解 (Construct Original Problem Solution)**:

   - 使用子問題的解來構建原始問題的解。

**例子 (Examples)**:

- **費波納契序列 (Fibonacci Sequence)**:

  - 傳統的遞迴方法可能會導致大量的重複計算，但通過動態規劃，我們可以保存中間結果以避免重複計算，從而大大提高效率。

- **背包問題 (Knapsack Problem)**:

  - 在背包問題中，我們試圖最大化背包中物品的總值，同時不超過背包的重量限制。通過動態規劃，我們可以找到最優解。

- **最長公共子序列 (Longest Common Subsequence, LCS)**:

  - 在最長公共子序列問題中，我們試圖找到兩個序列的最長公共子序列。通過動態規劃，我們可以高效地解決這個問題。

動態規劃是一個非常強大而靈活的算法設計技術，它可以應用於許多不同的計算問題，並且在許多情況下，都能得到高效的解決方案。

動態規劃（Dynamic Programming, DP）相關文章：

• NTNU Dynamic Programming
• Sean演算法筆記系列 — Dynamic programming 動態規劃