動態(tài)規(guī)劃
動態(tài)規(guī)劃是通過把原問題分解為相對簡單的子問題的方式來求解復(fù)雜問題的方法。
適用場景
動態(tài)規(guī)劃常常適用于有重疊子問題和最優(yōu)子結(jié)構(gòu)性質(zhì)的問題闹获。
問題特征
最優(yōu)子結(jié)構(gòu)：當(dāng)問題的最優(yōu)解包含了其子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)河哑。
重疊子問題：在用遞歸算法自頂向下解問題時避诽，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計算多次璃谨。動態(tài)規(guī)劃算法正是利用了這種子問題的重疊性質(zhì)沙庐，對每一個子問題只解一次，而后將其解保存在一個表格中佳吞，在以后盡可能多地利用這些子問題的解拱雏。
原理
若要解一個給定問題，我們需要解其不同部分（即子問題）底扳，再合并子問題的解以得出原問題的解铸抑。 通常許多子問題非常相似，為此動態(tài)規(guī)劃法試圖僅僅解決每個子問題一次衷模，從而減少計算量： 一旦某個給定子問題的解已經(jīng)算出鹊汛，則將其記憶化存儲，以便下次需要同一個子問題解之時直接查表阱冶。 這種做法在重復(fù)子問題的數(shù)目關(guān)于輸入的規(guī)模呈指數(shù)增長時特別有用刁憋。
用動態(tài)規(guī)劃解決問題的核心就在于填表，表格填寫完畢木蹬，最優(yōu)解也就找到至耻。
分治和動態(tài)規(guī)劃
共同點(diǎn)：
二者都要求原問題具有最優(yōu)子結(jié)構(gòu)性質(zhì),都是將原問題分而治之,分解成若干個規(guī)模較小(小到很容易解決的程序)的子問題.然后將子問題的解合并,形成原問題的解.
不同點(diǎn)：
1.分治法將分解后的子問題看成相互獨(dú)立的，通過用遞歸來做镊叁。
2.動態(tài)規(guī)劃將分解后的子問題理解為相互間有聯(lián)系,有重疊部分尘颓，需要記憶，通常用迭代來做晦譬。
解題步驟
尋找遞推表達(dá)式
