[演算法] 動態規劃（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)**: - 在最長公共子序列問題中，我們試圖找到兩個序列的最長公共子序列。通過動態規劃，我們...
