1. 基本思想： * 問題的最優解如果可以由子問題的最優解推導得到，則可以先求解子問題的最優解，在構造原問題的最優解； * 若子問題有較多的重復出現，則可以自底向上從最終子問題向原問題逐步求解。 2. 使用條件：**可分為多個相關子問題，子問題的解被重復使用** * Optimal substructure（優化子結構）： ``` 一個問題的優化解包含了子問題的優化解 縮小子問題集合，只需那些優化問題中包含的子問題，降低實現復雜性 我們可以自下而上的 ``` * Subteties（重疊子問題）：在問題的求解過程中，很多子問題的解將被多次使用。 3.動態規劃算法的設計步驟： * 分析優化解的結構 * 遞歸地定義最優解的代價 * 自底向上地計算優化解的代價保存之，并獲取構造最優解的信息 * 根據構造最優解的信息構造優化解 4.動態規劃特點: * 把原始問題劃分成一系列子問題； * 求解每個子問題僅一次，并將其結果保存在一個表中，以后用到時直接存取，不重復計算，節省計算時間 * 自底向上地計算。 * 整體問題最優解取決于子問題的最優解（狀態轉移方程）（將子問題稱為狀態，最終狀態的求解歸結為其他狀態的求解）