動態規劃的基本思想

動態規劃的基本思想是將待求解的問題分解成若干個相互聯絡的子問題，先求解子問題，然後從這些子問題的解得到原問題的解；對於重複出現的子問題，只在第一次遇到的時候對它進行求解，並把答案儲存起來，讓以後再次遇到時直接引用答案，不必重新求解。

動態規劃（ dynamic programming ）演算法是解決多階段決策過程最優化問題的一種常用方法，難度比較大，技巧性也很強。利用動態規劃演算法，可以優雅而高效地解決很多貪婪演算法或分治演算法不能解決的問題。