在介紹動態(tài)規(guī)劃的核心思想前撵孤，先看一道題槐雾。
題目分析：
令dp[i]代表有多少種方法可到達第i層航厚，
由于第i層只能由i-1走一層或者i-2走兩層達到尝艘，
故可得dp[i] = dp[i-2] + dp[i-1]赴穗，
很明顯根據(jù)題意dp[1] = 1,dp[2] = 2椎侠。
dp[0]哪去了第租？為了我們寫起來好看，浪費掉了我纪。
如果喜歡你也可以用dp[0] = 1, dp[1] = 2,只是最后結(jié)果是dp[i-1]而不是dp[i]就是了慎宾。
解法一：遞歸
public static int climbStairs_recursion(int n){
if(1 == n)
return 1;
else if(2 == n)
return 2;
return climbStairs_recursion(n-2) + climbStairs_recursion(n-1);
}
解法一分析
解法一存在一個問題，
因為dp[i] = dp[i-2] + dp[i-1]浅悉，則dp[i-1] = dp[i-3] + dp[i-2]趟据，
此刻dp[i-2]重復(fù)出現(xiàn)了兩次。
關(guān)鍵就在這里术健，這個重復(fù)的dp[i-2]并非重復(fù)一次這么簡單汹碱，
因為dp[i-2]又是由dp[i-4]+dp[i-3]得到，層層遞歸下去苛坚，將是2^(i-2)次函數(shù)調(diào)用比被，
舉一個例子，當(dāng)i=30時候泼舱，dp[i]將會調(diào)用函數(shù)1664079次等缀！
解法二：遞歸-動態(tài)規(guī)劃
public static int climbStairs_dp_recursion(int n, int[] dp){
if(1 == n)
return 1;
else if(2 == n)
return 2;
if(0 == dp[n])
dp[n] = climbStairs_dp_recursion(n-2, dp) + climbStairs_dp_recursion(n-1, dp);
return dp[n];
}
解法二分析
1.使用一個數(shù)組來緩存了中間結(jié)果，防止了“重疊子問題”的重復(fù)計算娇昙。
2.解法二依然存在一個問題尺迂，就是在于“遞歸”這種寫法，遞歸產(chǎn)生的函數(shù)調(diào)用將消耗線程棧內(nèi)存冒掌。
使用-Xss180k作為虛擬機啟動參數(shù)將線程棧設(shè)置為180k（jvm允許的最小值）噪裕，
并將問題規(guī)模n設(shè)置為3000，就會出現(xiàn)Stack Over flow股毫。
解法三：循環(huán)-動態(tài)規(guī)劃
public static int climbStairs_dp_loop(int n){
if(1 == n)
return 1;
else if(2 == n)
return 2;
int[] dp = new int[n+1];
int res = 0;
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i < n+1; i++) {
res = dp[i] = dp[i-2] + dp[i-1];
}
return res;
}
解法三分析
1.解決方法是改為循環(huán)膳音，
因為遞歸和循環(huán)永遠可以相互轉(zhuǎn)換，請不要懷疑“永遠”這個詞的嚴謹性铃诬。
2.最后還有一個可優(yōu)化的點祭陷，內(nèi)存使用苍凛。
我們使用dp[i] = dp[i-2] + dp[i-1]這個式子，循環(huán)遞推出結(jié)果兵志，
dp[i]使我們想要的結(jié)果醇蝴，而只需要dp[i-2]和dp[i-1]得到，
然而我們卻保留了i個也就是所有遞推過程的中間結(jié)果想罕，顯然這是一種浪費悠栓。
解法四：循環(huán)-動態(tài)規(guī)劃-內(nèi)存優(yōu)化
public static int climbStairs_dp_loop_lessMemory(int n){
if(1 == n)
return 1;
else if(2 == n)
return 2;
int res = 0;
int temp1 = 1;
int temp2 = 2;
for (int i = 3; i < n+1; i++) {
res = temp1 + temp2;
temp1 = temp2;
temp2 = res;
}
return res;
}
解法四分析
通過兩個變量的交替更新使用，達到了節(jié)約內(nèi)存的目的按价，
這種不斷更新兩個變量的做法惭适，就像將整個數(shù)組“滾動”起來了一樣，在動態(tài)規(guī)劃中稱為“滾動數(shù)組”俘枫。
這里不用擔(dān)心我們丟掉的結(jié)果腥沽，因為題目只求最后的值。
總結(jié)
1.將結(jié)果集合之間的關(guān)系描述為“動態(tài)轉(zhuǎn)換方程”鸠蚪。
動態(tài)規(guī)劃的所有核心都在這一步今阳。
在做dp時，
不要關(guān)注數(shù)據(jù)和最終結(jié)果的關(guān)系茅信。
關(guān)注結(jié)果集合之間的關(guān)系盾舌！
結(jié)果集合指什么，此題中所有dp[i]的值的集合就是結(jié)果集合蘸鲸。
我們找到的dp[i] = dp[i-2] + dp[i-1]妖谴，就是結(jié)果集合之間的關(guān)系。
這個關(guān)系就是"動態(tài)轉(zhuǎn)換方程"酌摇。
2.構(gòu)造遞推初始項膝舅。
3.緩存推導(dǎo)過程中的“重疊子問題”，防止重復(fù)計算窑多。
4."滾動使用變量或數(shù)組"是常見的dp內(nèi)存優(yōu)化方式仍稀。
相應(yīng)例題的 Github
