爬樓梯問題
問題描述：
現(xiàn)在總共有10層臺(tái)階磺樱，一只青蛙一次只能跳一階或兩階。問總共有多少種跳法婆咸？
??分析一波： 青蛙即將一步到達(dá)第10階前只有兩種情況竹捉，即：1.從第9階一階跳上去；2.從第8階兩階跳上去尚骄。如果用 F(n)表示青蛙跳到第n階所需要的步數(shù)块差，則有：
F(1) = 1 , 當(dāng) n = 1 時(shí)
F(2) = 2 , 當(dāng) n = 2 時(shí)
F(n) = F(n - 1) + F(n - 2), 當(dāng) n > 2 時(shí)
所以， 二話不說先來一發(fā)遞歸：
public static int numsOfStairs(int n) {
if (n == 1) {
return 1;
} else if (n == 2) {
return 2;
} else if (n > 2) {
return numsOfStairs(n - 1) + numsOfStairs(n - 2);
} else {
return 0;
}
}
我將初始層數(shù)設(shè)置為40倔丈，總共耗時(shí)328毫秒憨闰。如果設(shè)置為100層...反正我沒等我電腦把結(jié)果跑完...執(zhí)行結(jié)果如下：
??都說遞歸慢...遞歸慢，遞歸為何慢需五？為啥還要使用遞歸呢鹉动？首先，為什么要是用遞歸警儒，這很容易去解釋训裆，因?yàn)樗Z句簡(jiǎn)潔、邏輯表達(dá)清晰蜀铲，寫出來更能讓人去理解边琉，一目了然。那為什么執(zhí)行地慢记劝？是因?yàn)槿绻f歸層數(shù)比較深变姨，需要增加額外的堆棧去處理，這樣很容易造成 堆棧溢出Ｑ岢蟆定欧！對(duì)于遞歸的每一層，都需要堆棧去存儲(chǔ)調(diào)用參數(shù)和中間變量怒竿，所以會(huì)增加很多額外的系統(tǒng)開銷砍鸠。
??那有沒有辦法既能使代碼簡(jiǎn)潔，又能讓效率提升呢耕驰？ 嗯確實(shí)是有的爷辱，可以采取一種叫做尾遞歸的方法。怎么去理解尾遞歸呢朦肘？我這里對(duì)其概念不做過多介紹饭弓，一句話總結(jié)什么是尾遞歸： 將當(dāng)前計(jì)算結(jié)果作為參數(shù)傳入下一層 。
改用尾遞歸的代碼如下：
/**
*
* @param n
* @param init1 初始值1
* @param init2 初始值2
* @return
*/
public static int numsOfStairs(int n, int init1, int init2) {
if (n == 1) {
return init1;
} else if (n > 1) {
return numsOfStairs(n - 1, init2, init1 + init2);
} else {
return 0;
}
}
再貼上初始值設(shè)為40時(shí)的測(cè)試結(jié)果：
??執(zhí)行速度是不是快了不少媒抠？正常的遞歸需要一層層向下進(jìn)行遞歸弟断，然后再向上返回結(jié)果。而尾遞歸只需要向下進(jìn)行遞歸趴生，每一層遞歸時(shí)都進(jìn)行計(jì)算阀趴，最后再返回一次結(jié)果昏翰。 除此之外，尾遞歸以犧牲兩個(gè)額外空間的方式刘急，來減少了中間變量的存儲(chǔ)和返回矩父。這樣一來， 不僅效率大大提升排霉，同時(shí)也避免了內(nèi)存溢出窍株。
??那么懊蒸，接下來就進(jìn)入正題悔常，引入動(dòng)態(tài)規(guī)劃算法。使用動(dòng)態(tài)規(guī)劃算法旋讹，可以讓每個(gè)狀態(tài)都只計(jì)算一次瑰钮，將結(jié)果保存下來進(jìn)行下一次的計(jì)算冒滩，同時(shí)無需堆棧來保存遞歸現(xiàn)場(chǎng)。
動(dòng)態(tài)規(guī)劃算法
??動(dòng)態(tài)規(guī)劃算法是通過拆分問題浪谴，定義問題狀態(tài)和狀態(tài)之間的關(guān)系开睡，使得問題能夠以遞推或者分治的方式去解決。
??動(dòng)態(tài)規(guī)劃算法的基本思想與分治法類似苟耻，也是將待求解的問題分解為若干個(gè)子問題（階段）篇恒，按順序求解子階段，前一子問題的解凶杖，為后一子問題的求解提供了有用的信息胁艰。在求解任一子問題時(shí)，列出各種可能的局部解智蝠，通過決策保留那些有可能達(dá)到最優(yōu)的局部解腾么，丟棄其他局部解。依次解決各子問題杈湾，最后一個(gè)子問題就是初始問題的解解虱。
??由于動(dòng)態(tài)規(guī)劃解決的問題多數(shù)有重疊子問題這個(gè)特點(diǎn)，為減少重復(fù)計(jì)算漆撞，對(duì)每一個(gè)子問題只解一次殴泰，將其不同階段的不同狀態(tài)保存在一個(gè)二維數(shù)組中。（百度百科）
??因?yàn)槊恳淮味加?code>F（n） = F（n-1）+ F（n-2）叫挟，因此我們需要用兩個(gè)臨時(shí)變量來存儲(chǔ)中間結(jié)果艰匙。同樣是爬樓梯問題限煞，使用動(dòng)態(tài)規(guī)劃后的方案如下：
public static int numsOfStairs(int n) {
int fn1 = 1, fn2 = 2; // 分別存儲(chǔ) f(n - 1) 和 f(n - 2)
if (n < 3) {
return n;
} else if (n >= 3) {
int sum = 0;
for (int i = 3; i <= n; i++) {
sum = fn1 + fn2;
fn1 = fn2;
fn2 = sum;
}
return sum;
} else {
return 0;
}
}
動(dòng)態(tài)規(guī)劃算法的適用條件：
- 最優(yōu)化原理（最優(yōu)子結(jié)構(gòu)性質(zhì)）: 一個(gè)最優(yōu)策略的子策略是最優(yōu)的抹恳。一個(gè)問題滿足最優(yōu)化原理又稱其具有最優(yōu)子結(jié)構(gòu)性質(zhì)。
- 無后效性： 各階段的狀態(tài)都是對(duì)過去歷史的總結(jié)署驻，而只有現(xiàn)階段狀態(tài)能影響未來的決策奋献，其他之前的狀態(tài)都無法影響未來的決策健霹。
- 子問題的重疊性: 動(dòng)態(tài)規(guī)劃將原來具有指數(shù)級(jí)時(shí)間復(fù)雜度的搜索算法改進(jìn)成了具有多項(xiàng)式時(shí)間復(fù)雜度的算法。其中的關(guān)鍵在于解決冗余瓶蚂，這是動(dòng)態(tài)規(guī)劃算法的根本目的糖埋。動(dòng)態(tài)規(guī)劃實(shí)質(zhì)上是一種以空間換時(shí)間的技術(shù)，它在實(shí)現(xiàn)的過程中窃这，不得不存儲(chǔ)產(chǎn)生過程中的各種狀態(tài)瞳别，所以它的空間復(fù)雜度要大于其它的算法。
