**1. 證明優化子結構** 對于問題的優化子結構，給出問題具有優化子結構的解代價，利用反證法，假設上解不是最優的，則存在另外一個解，其解優于上解，這與上解是最優的矛盾，于是該問題具有優化子結構。 證明優化子結構問題主要利用反證法。 **2. 證明重復子問題** 給出問題的遞歸公式則重疊子問題鍀證。 **3. 遞歸的定義最優解的代價** 給出最有解的代價遞歸公式，利于代碼編寫。 **4. 自底向上計算最優解的代價** 一般利用二維矩陣求解代價，或一行一行計算代價，或按列計算代價，或按照對角線逐級計算代價。 **5. 構造最優解** 根據最有接的代價矩陣信息，編寫函數構造最優解。