對動態(tài)規(guī)劃的思考

如何確定一類的算法問題可以用動態(tài)規(guī)劃的方式，首先就是抓住算法題的最優(yōu)結(jié)果，是否可以從前往后，從上到下，算法的最優(yōu)結(jié)果是否可以由先前的最優(yōu)化結(jié)果推出來，也就是最優(yōu)的子結(jié)構(gòu)，用dp數(shù)組的形式逐漸遞推到最終的最優(yōu)結(jié)果。例如01背包問題，數(shù)塔問題。

還有一種是問題具有重復的計算，問題的求解種重復的計算浪費了大量的資源。這時候就是屬于有重復的子問題，可以用一個數(shù)組dp保存已經(jīng)計算過的結(jié)果，以減少時間的復雜度，這也是一種剪枝的技巧。例如遞歸的求解斐波那契數(shù)列。

if (dp[i]==1){

表示已經(jīng)計算過了，直接就使用dp[i]；

}else{

計算它的結(jié)果；

}