動態規劃的基本要素

動態規劃的基本要素如下：

1、最優子結構。當問題的最優解包含了其子問題的最優解時，稱該問題具有最優子結構性質。問題的最優子結構性質提供了該問題可用動態規劃算法求解的重要線索。在動態規劃算法中，利用問題的最優子結構性質，以自底向上的方式遞歸地從子問題的最優解逐步構造出整個問題的最優解。

2、重疊子問題。可用動態規劃算法求解的問題應具備的另一個基本要素是子問題的重疊性質。在用遞歸算法自頂向下求解問題時，每次產生的子問題並不總是新問題，有些子問題被反覆計算多次。動態規劃算法正是利用了這種子問題的重疊性質，對每一個子問題只解一次，而後將其解儲存在一個表格中，當再次需要此子問題時，只要簡單地用常數時間檢視一下結果。通常，不同的子問題個數隨問題的大小呈多項式增長。因此，用動態規劃算法通常只需要多項式時間，從而獲得較高的解題效率。