對(duì)動(dòng)態(tài)規(guī)劃的思考
如何確定一類(lèi)的算法問(wèn)題可以用動(dòng)態(tài)規(guī)劃的方式，首先就是抓住算法題的最優(yōu)結(jié)果留晚，是否可以從前往后，從上到下，算法的最優(yōu)結(jié)果是否可以由先前的最優(yōu)化結(jié)果推出來(lái)错维，也就是最優(yōu)的子結(jié)構(gòu)奖地，用dp數(shù)組的形式逐漸遞推到最終的最優(yōu)結(jié)果。例如01背包問(wèn)題赋焕，數(shù)塔問(wèn)題参歹。
還有一種是問(wèn)題具有重復(fù)的計(jì)算，問(wèn)題的求解種重復(fù)的計(jì)算浪費(fèi)了大量的資源隆判。這時(shí)候就是屬于有重復(fù)的子問(wèn)題犬庇，可以用一個(gè)數(shù)組dp保存已經(jīng)計(jì)算過(guò)的結(jié)果，以減少時(shí)間的復(fù)雜度侨嘀，這也是一種剪枝的技巧臭挽。例如遞歸的求解斐波那契數(shù)列。
if (dp[i]==1){
表示已經(jīng)計(jì)算過(guò)了咬腕，直接就使用dp[i]欢峰；
}else{
計(jì)算它的結(jié)果；
}
