動態(tài)規(guī)劃的基本要素如下：

　　1、最優(yōu)子結(jié)構(gòu)。當(dāng)問題的最優(yōu)解包含了其子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)提供了該問題可用動態(tài)規(guī)劃算法求解的重要線索。在動態(tài)規(guī)劃算法中，利用問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，以自底向上的方式遞歸地從子問題的最優(yōu)解逐步構(gòu)造出整個問題的最優(yōu)解。

　　2、重疊子問題。可用動態(tài)規(guī)劃算法求解的問題應(yīng)具備的另一個基本要素是子問題的重疊性質(zhì)。在用遞歸算法自頂向下求解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計算多次。動態(tài)規(guī)劃算法正是利用了這種子問題的重疊性質(zhì)，對每一個子問題只解一次，而后將其解保存在一個表格中，當(dāng)再次需要此子問題時，只要簡單地用常數(shù)時間查看一下結(jié)果。通常，不同的子問題個數(shù)隨問題的大小呈多項式增長。因此，用動態(tài)規(guī)劃算法通常只需要多項式時間，從而獲得較高的解題效率。

聲明：本網(wǎng)頁內(nèi)容旨在傳播知識，若有侵權(quán)等問題請及時與本網(wǎng)聯(lián)系，我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com