動(dòng)態(tài)規(guī)劃的關(guān)鍵點(diǎn)：
- 最優(yōu)化原理，也就是最優(yōu)子結(jié)構(gòu)性質(zhì)佳恬。這指的是一個(gè)最優(yōu)化策略具有這樣的性質(zhì)捏境，無(wú)論過(guò)去狀態(tài)和決策如何于游，對(duì)前面的決策所形成的狀態(tài)而言，余下的決策必須構(gòu)成最優(yōu)策略垫言，簡(jiǎn)單來(lái)說(shuō)就是一個(gè)最優(yōu)化策略的子策略總是最優(yōu)的贰剥，如果一個(gè)問(wèn)題滿(mǎn)足最優(yōu)化原理，就稱(chēng)其有最優(yōu)子結(jié)構(gòu)性質(zhì)筷频。
- 無(wú)后效性蚌成，指的是某個(gè)狀態(tài)下的決策的收益，只與狀態(tài)和決策相關(guān)凛捏，與達(dá)到該狀態(tài)的方式無(wú)關(guān)担忧。
- 子問(wèn)題的重疊性，動(dòng)態(tài)規(guī)劃將原來(lái)指數(shù)級(jí)的暴力搜索算法改進(jìn)到了具有多項(xiàng)式時(shí)間復(fù)雜度的算法坯癣，其中的關(guān)鍵在于解決了冗余瓶盛、重復(fù)計(jì)算的問(wèn)題，這是動(dòng)態(tài)規(guī)劃算法的根本目的示罗。
- 總體來(lái)說(shuō)惩猫，動(dòng)態(tài)規(guī)劃算法就是一系列以空間換取時(shí)間的算法。
動(dòng)態(tài)規(guī)劃使用
下面通過(guò)遞歸方式計(jì)算問(wèn)題斐波那契數(shù)列（Fibonacci sequence）來(lái)闡述分治法不是銀彈蚜点。
斐波那契數(shù)列指的是這樣一個(gè)數(shù)列 0,1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233帆锋，377，610禽额，987锯厢，1597，2584脯倒，4181实辑，6765，10946藻丢，17711剪撬，28657，46368........
斐波那契數(shù)列數(shù)學(xué)表示
這個(gè)數(shù)列從第3項(xiàng)開(kāi)始悠反，每一項(xiàng)都等于前兩項(xiàng)之和残黑。
下面給出遞歸實(shí)現(xiàn)的代碼：
/**
* 求解Fibonacci數(shù)列中第n個(gè)元素的值
* @param n 斐波那契數(shù)列中的位置
* @return Fibonacci數(shù)列中第n個(gè)元素的值
*/
public int fibonacci(int n) {
if(n<2) return n;
if(n>=2) {
return fibonacci(n-1)+fibonacci(n-2);
}
return -1;
}
通過(guò)控制臺(tái)驗(yàn)證下算法的計(jì)算結(jié)果和計(jì)算用時(shí)。
fibonacci 0 is 0 計(jì)算用時(shí) 0ms
fibonacci 1 is 1 計(jì)算用時(shí) 1ms
fibonacci 2 is 1 計(jì)算用時(shí) 0ms
fibonacci 3 is 2 計(jì)算用時(shí) 0ms
fibonacci 4 is 3 計(jì)算用時(shí) 0ms
fibonacci 5 is 5 計(jì)算用時(shí) 0ms
fibonacci 6 is 8 計(jì)算用時(shí) 0ms
fibonacci 7 is 13 計(jì)算用時(shí) 0ms
fibonacci 8 is 21 計(jì)算用時(shí) 0ms
fibonacci 9 is 34 計(jì)算用時(shí) 0ms
fibonacci 10 is 55 計(jì)算用時(shí) 0ms
fibonacci 11 is 89 計(jì)算用時(shí) 0ms
fibonacci 12 is 144 計(jì)算用時(shí) 0ms
fibonacci 13 is 233 計(jì)算用時(shí) 0ms
fibonacci 14 is 377 計(jì)算用時(shí) 0ms
fibonacci 15 is 610 計(jì)算用時(shí) 0ms
fibonacci 16 is 987 計(jì)算用時(shí) 0ms
fibonacci 17 is 1597 計(jì)算用時(shí) 1ms
fibonacci 18 is 2584 計(jì)算用時(shí) 0ms
fibonacci 19 is 4181 計(jì)算用時(shí) 0ms
fibonacci 20 is 6765 計(jì)算用時(shí) 0ms
fibonacci 21 is 10946 計(jì)算用時(shí) 0ms
fibonacci 22 is 17711 計(jì)算用時(shí) 0ms
fibonacci 23 is 28657 計(jì)算用時(shí) 1ms
fibonacci 24 is 46368 計(jì)算用時(shí) 0ms
fibonacci 25 is 75025 計(jì)算用時(shí) 1ms
fibonacci 26 is 121393 計(jì)算用時(shí) 1ms
fibonacci 27 is 196418 計(jì)算用時(shí) 1ms
fibonacci 28 is 317811 計(jì)算用時(shí) 3ms
fibonacci 29 is 514229 計(jì)算用時(shí) 2ms
fibonacci 30 is 832040 計(jì)算用時(shí) 4ms
fibonacci 31 is 1346269 計(jì)算用時(shí) 8ms
fibonacci 32 is 2178309 計(jì)算用時(shí) 11ms
fibonacci 33 is 3524578 計(jì)算用時(shí) 20ms
fibonacci 34 is 5702887 計(jì)算用時(shí) 29ms
fibonacci 35 is 9227465 計(jì)算用時(shí) 46ms
fibonacci 36 is 14930352 計(jì)算用時(shí) 73ms
fibonacci 37 is 24157817 計(jì)算用時(shí) 127ms
fibonacci 38 is 39088169 計(jì)算用時(shí) 186ms
fibonacci 39 is 63245986 計(jì)算用時(shí) 306ms
fibonacci 40 is 102334155 計(jì)算用時(shí) 505ms
fibonacci 41 is 165580141 計(jì)算用時(shí) 816ms
fibonacci 42 is 267914296 計(jì)算用時(shí) 1298ms
fibonacci 43 is 433494437 計(jì)算用時(shí) 2110ms
fibonacci 44 is 701408733 計(jì)算用時(shí) 3423ms
fibonacci 45 is 1134903170 計(jì)算用時(shí) 5525ms
fibonacci 46 is 1836311903 計(jì)算用時(shí) 9013ms
fibonacci 47 is -1323752223 計(jì)算用時(shí) 14382ms
可以看出斋否，n=47是出現(xiàn)了int類(lèi)型的越界（Integer.MAX_VALUE is 2147483647）這里需要注意梨水，計(jì)算用時(shí)達(dá)到了恐怖的14秒多。斐波那契數(shù)列的值隨著增大進(jìn)行指數(shù)級(jí)的增長(zhǎng)茵臭，運(yùn)行事件也是指數(shù)級(jí)的增長(zhǎng)（n越大越能看出這一點(diǎn)）疫诽。
斐波那契數(shù)列-遞歸方法調(diào)用過(guò)程
動(dòng)態(tài)規(guī)劃版本
正如魯迅先生的《狂人日記》中，孔乙己"回"字的四種寫(xiě)法。動(dòng)態(tài)規(guī)劃算法有兩種等價(jià)的實(shí)現(xiàn)方法奇徒。
- 帶備忘的自頂向下法（top-down with memoization）雏亚，此方法仍按自然的遞歸形式編寫(xiě)過(guò)程，但過(guò)程會(huì)保存每個(gè)子問(wèn)題的解（通常保存在一個(gè)數(shù)組或者散列表中）摩钙。當(dāng)需要一個(gè)子問(wèn)題的解時(shí)罢低，過(guò)程首先檢查是否已經(jīng)保存過(guò)此解。如果是胖笛，則直接返回保存的值奕短，從而節(jié)省了計(jì)算時(shí)間，否則匀钧，按通常的方式計(jì)算這個(gè)子問(wèn)題翎碑。我們稱(chēng)這個(gè)遞歸過(guò)程是帶備忘的（memoized）,因?yàn)樗坝涀 绷酥坝?jì)算出的結(jié)果。
以斐波那契數(shù)列的解法為例之斯，代碼如下：
long[] memo=new long[memoSize];
public long topdown(int n) {
if(n<0) return -1;
if(n<2) return n;
if(memo[n]>0) {
return memo[n];
}else {
return memo[n]=topdown(n-1)+topdown(n-2);
}
通過(guò)控制臺(tái)驗(yàn)證下算法的計(jì)算結(jié)果和計(jì)算用時(shí)日杈。
fibonacci 0 is 0 計(jì)算用時(shí) 0ms
fibonacci 1 is 1 計(jì)算用時(shí) 0ms
fibonacci 2 is 1 計(jì)算用時(shí) 0ms
fibonacci 3 is 2 計(jì)算用時(shí) 1ms
fibonacci 4 is 3 計(jì)算用時(shí) 0ms
fibonacci 5 is 5 計(jì)算用時(shí) 0ms
fibonacci 6 is 8 計(jì)算用時(shí) 0ms
fibonacci 7 is 13 計(jì)算用時(shí) 0ms
fibonacci 8 is 21 計(jì)算用時(shí) 0ms
fibonacci 9 is 34 計(jì)算用時(shí) 0ms
fibonacci 10 is 55 計(jì)算用時(shí) 0ms
fibonacci 11 is 89 計(jì)算用時(shí) 0ms
fibonacci 12 is 144 計(jì)算用時(shí) 0ms
fibonacci 13 is 233 計(jì)算用時(shí) 0ms
fibonacci 14 is 377 計(jì)算用時(shí) 0ms
fibonacci 15 is 610 計(jì)算用時(shí) 0ms
fibonacci 16 is 987 計(jì)算用時(shí) 0ms
fibonacci 17 is 1597 計(jì)算用時(shí) 0ms
fibonacci 18 is 2584 計(jì)算用時(shí) 0ms
fibonacci 19 is 4181 計(jì)算用時(shí) 0ms
fibonacci 20 is 6765 計(jì)算用時(shí) 0ms
fibonacci 21 is 10946 計(jì)算用時(shí) 0ms
fibonacci 22 is 17711 計(jì)算用時(shí) 0ms
fibonacci 23 is 28657 計(jì)算用時(shí) 0ms
fibonacci 24 is 46368 計(jì)算用時(shí) 0ms
fibonacci 25 is 75025 計(jì)算用時(shí) 0ms
fibonacci 26 is 121393 計(jì)算用時(shí) 0ms
fibonacci 27 is 196418 計(jì)算用時(shí) 0ms
fibonacci 28 is 317811 計(jì)算用時(shí) 0ms
fibonacci 29 is 514229 計(jì)算用時(shí) 0ms
fibonacci 30 is 832040 計(jì)算用時(shí) 0ms
fibonacci 31 is 1346269 計(jì)算用時(shí) 0ms
fibonacci 32 is 2178309 計(jì)算用時(shí) 0ms
fibonacci 33 is 3524578 計(jì)算用時(shí) 0ms
fibonacci 34 is 5702887 計(jì)算用時(shí) 0ms
fibonacci 35 is 9227465 計(jì)算用時(shí) 0ms
fibonacci 36 is 14930352 計(jì)算用時(shí) 0ms
fibonacci 37 is 24157817 計(jì)算用時(shí) 0ms
fibonacci 38 is 39088169 計(jì)算用時(shí) 0ms
fibonacci 39 is 63245986 計(jì)算用時(shí) 0ms
fibonacci 40 is 102334155 計(jì)算用時(shí) 0ms
fibonacci 41 is 165580141 計(jì)算用時(shí) 0ms
fibonacci 42 is 267914296 計(jì)算用時(shí) 0ms
fibonacci 43 is 433494437 計(jì)算用時(shí) 0ms
fibonacci 44 is 701408733 計(jì)算用時(shí) 0ms
fibonacci 45 is 1134903170 計(jì)算用時(shí) 0ms
fibonacci 46 is 1836311903 計(jì)算用時(shí) 0ms
fibonacci 47 is 2971215073 計(jì)算用時(shí) 0ms
- 自底向上法（bottom-up method），這種方法一般需要恰當(dāng)定義子問(wèn)題的“規(guī)挠铀ⅲ”的概念莉擒，使得任何子問(wèn)題的求解只依賴(lài)“更小的”子問(wèn)題的求解。因而我們可以將子問(wèn)題按規(guī)模排序瘫絮，按由小到大的順序進(jìn)行求解涨冀。當(dāng)求解某個(gè)子問(wèn)題時(shí)，它所依賴(lài)的那些更小的子問(wèn)題都已經(jīng)求解完畢麦萤，結(jié)果已經(jīng)保存鹿鳖。每個(gè)子問(wèn)題只需求解依次，當(dāng)我們求解它（也是第一次遇到它）時(shí)壮莹，它的所有前提子問(wèn)題都已求解完成翅帜。
動(dòng)態(tài)規(guī)劃的解法-自底向上法
long[] memo=new long[memoSize];
public long bottomup(int n) {
if(n<0) return -1;
if(n<=1) return n;
memo[0]=0;
memo[1]=1;
if(n>1) {
for(int i=2;i<=n;i++) {
memo[i]=memo[i-1]+memo[i-2];
}
}
return memo[n];
}
通過(guò)控制臺(tái)驗(yàn)證下算法的計(jì)算結(jié)果和計(jì)算用時(shí)。
fibonacci 0 is 0 計(jì)算用時(shí) 0ms
fibonacci 1 is 1 計(jì)算用時(shí) 0ms
fibonacci 2 is 1 計(jì)算用時(shí) 0ms
fibonacci 3 is 2 計(jì)算用時(shí) 0ms
fibonacci 4 is 3 計(jì)算用時(shí) 0ms
fibonacci 5 is 5 計(jì)算用時(shí) 0ms
fibonacci 6 is 8 計(jì)算用時(shí) 0ms
fibonacci 7 is 13 計(jì)算用時(shí) 0ms
fibonacci 8 is 21 計(jì)算用時(shí) 0ms
fibonacci 9 is 34 計(jì)算用時(shí) 0ms
fibonacci 10 is 55 計(jì)算用時(shí) 0ms
fibonacci 11 is 89 計(jì)算用時(shí) 0ms
fibonacci 12 is 144 計(jì)算用時(shí) 0ms
fibonacci 13 is 233 計(jì)算用時(shí) 0ms
fibonacci 14 is 377 計(jì)算用時(shí) 0ms
fibonacci 15 is 610 計(jì)算用時(shí) 0ms
fibonacci 16 is 987 計(jì)算用時(shí) 0ms
fibonacci 17 is 1597 計(jì)算用時(shí) 0ms
fibonacci 18 is 2584 計(jì)算用時(shí) 0ms
fibonacci 19 is 4181 計(jì)算用時(shí) 0ms
fibonacci 20 is 6765 計(jì)算用時(shí) 0ms
fibonacci 21 is 10946 計(jì)算用時(shí) 0ms
fibonacci 22 is 17711 計(jì)算用時(shí) 0ms
fibonacci 23 is 28657 計(jì)算用時(shí) 0ms
fibonacci 24 is 46368 計(jì)算用時(shí) 0ms
fibonacci 25 is 75025 計(jì)算用時(shí) 0ms
fibonacci 26 is 121393 計(jì)算用時(shí) 0ms
fibonacci 27 is 196418 計(jì)算用時(shí) 0ms
fibonacci 28 is 317811 計(jì)算用時(shí) 0ms
fibonacci 29 is 514229 計(jì)算用時(shí) 0ms
fibonacci 30 is 832040 計(jì)算用時(shí) 0ms
fibonacci 31 is 1346269 計(jì)算用時(shí) 0ms
fibonacci 32 is 2178309 計(jì)算用時(shí) 0ms
fibonacci 33 is 3524578 計(jì)算用時(shí) 0ms
fibonacci 34 is 5702887 計(jì)算用時(shí) 0ms
fibonacci 35 is 9227465 計(jì)算用時(shí) 0ms
fibonacci 36 is 14930352 計(jì)算用時(shí) 0ms
fibonacci 37 is 24157817 計(jì)算用時(shí) 0ms
fibonacci 38 is 39088169 計(jì)算用時(shí) 0ms
fibonacci 39 is 63245986 計(jì)算用時(shí) 0ms
fibonacci 40 is 102334155 計(jì)算用時(shí) 0ms
fibonacci 41 is 165580141 計(jì)算用時(shí) 0ms
fibonacci 42 is 267914296 計(jì)算用時(shí) 0ms
fibonacci 43 is 433494437 計(jì)算用時(shí) 0ms
fibonacci 44 is 701408733 計(jì)算用時(shí) 0ms
fibonacci 45 is 1134903170 計(jì)算用時(shí) 0ms
fibonacci 46 is 1836311903 計(jì)算用時(shí) 0ms
fibonacci 47 is 2971215073 計(jì)算用時(shí) 0ms
總結(jié)
同樣規(guī)模的斐波那契數(shù)列的計(jì)算問(wèn)題命满，動(dòng)態(tài)規(guī)劃版本的都能在很短的時(shí)間內(nèi)計(jì)算完畢涝滴，遞歸的解決方案，在小于50的情況下就出現(xiàn)了十幾秒的計(jì)算情況胶台，動(dòng)態(tài)規(guī)劃的運(yùn)行時(shí)間的提升很明顯歼疮。
動(dòng)態(tài)規(guī)劃解決走臺(tái)階問(wèn)題
有n級(jí)臺(tái)階，每次上一級(jí)或者兩級(jí)诈唬，問(wèn)有多少種走完n級(jí)臺(tái)階的方法韩脏。
分析：動(dòng)態(tài)規(guī)劃的實(shí)現(xiàn)的關(guān)鍵在于能不能準(zhǔn)確合理的用動(dòng)態(tài)規(guī)劃表來(lái)抽象出 實(shí)際問(wèn)題。在這個(gè)問(wèn)題上讯榕，我們讓f(n)表示走上n級(jí)臺(tái)階的方法數(shù)骤素。
那么當(dāng)n為1時(shí)匙睹，f(n) = 1,n為2時(shí)愚屁，f(n) =2,就是說(shuō)當(dāng)臺(tái)階只有一級(jí)的時(shí)候济竹，方法數(shù)是一種，臺(tái)階有兩級(jí)的時(shí)候霎槐，方法數(shù)為2送浊。那么當(dāng)我們要走上n級(jí)臺(tái)階，必然是從n-1級(jí)臺(tái)階邁一步或者是從n-2級(jí)臺(tái)階邁兩步丘跌，所以到達(dá)n級(jí)臺(tái)階的方法數(shù)必然是到達(dá)n-1級(jí)臺(tái)階的方法數(shù)加上到達(dá)n-2級(jí)臺(tái)階的方法數(shù)之和袭景。即f(n) = f(n-1)+f(n-2)，我們用dp[n]來(lái)表示動(dòng)態(tài)規(guī)劃表闭树，dp[i],i>0,i<=n,表示到達(dá)i級(jí)臺(tái)階的方法數(shù)耸棒。
動(dòng)態(tài)規(guī)劃的解法-自底向上法
long[] memo=new long[memoSize];
public long stepBottomup(int n) {
if(n<0) return 0;
if(n==1) return 1;
if(n==2) return 2;
memo[0]=1;
memo[1]=2;
if(n>1) {
for(int i=2;i<n;i++) {
memo[i]=memo[i-1]+memo[i-2];
}
}
return memo[n-1];
}
通過(guò)控制臺(tái)驗(yàn)證下算法的計(jì)算結(jié)果和計(jì)算用時(shí)。
走臺(tái)階方案數(shù) 樓梯數(shù) 1 走法 is 1 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 2 走法 is 2 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 3 走法 is 3 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 4 走法 is 5 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 5 走法 is 8 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 6 走法 is 13 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 7 走法 is 21 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 8 走法 is 34 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 9 走法 is 55 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 10 走法 is 89 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 11 走法 is 144 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 12 走法 is 233 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 13 走法 is 377 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 14 走法 is 610 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 15 走法 is 987 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 16 走法 is 1597 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 17 走法 is 2584 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 18 走法 is 4181 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 19 走法 is 6765 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 20 走法 is 10946 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 21 走法 is 17711 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 22 走法 is 28657 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 23 走法 is 46368 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 24 走法 is 75025 計(jì)算用時(shí) 1ms
走臺(tái)階方案數(shù) 樓梯數(shù) 25 走法 is 121393 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 26 走法 is 196418 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 27 走法 is 317811 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 28 走法 is 514229 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 29 走法 is 832040 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 30 走法 is 1346269 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 31 走法 is 2178309 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 32 走法 is 3524578 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 33 走法 is 5702887 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 34 走法 is 9227465 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 35 走法 is 14930352 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 36 走法 is 24157817 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 37 走法 is 39088169 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 38 走法 is 63245986 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 39 走法 is 102334155 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 40 走法 is 165580141 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 41 走法 is 267914296 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 42 走法 is 433494437 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 43 走法 is 701408733 計(jì)算用時(shí) 1ms
走臺(tái)階方案數(shù) 樓梯數(shù) 44 走法 is 1134903170 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 45 走法 is 1836311903 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 46 走法 is 2971215073 計(jì)算用時(shí) 0ms
走臺(tái)階方案數(shù) 樓梯數(shù) 47 走法 is 4807526976 計(jì)算用時(shí) 0ms
這里只給出其中的一種解法报辱，至于另一種解法与殃，大家嘗試的寫(xiě)下。
以上碍现，謝謝閱讀幅疼，希望你有所收獲！
算法導(dǎo)論公開(kāi)課筆記（一）算法分析與設(shè)計(jì)
算法導(dǎo)論公開(kāi)課筆記（二）快速排序和隨機(jī)化算法
算法導(dǎo)論公開(kāi)課筆記（三）線(xiàn)性時(shí)間排序
算法導(dǎo)論公開(kāi)課筆記（四）順序統(tǒng)計(jì)昼接、中值
動(dòng)態(tài)規(guī)劃算法
