直奔主題

算法題是在面試過(guò)程中考察候選人邏輯思維能力、手寫(xiě)代碼能力的一種方式，因?yàn)橛幸痪涔旁?huà)說(shuō)的好：“說(shuō)一千道一萬(wàn)，不如寫(xiě)段代碼看一看”。

今天我們就來(lái)個(gè)單刀直入，直奔主題，從一個(gè)真實(shí)面試題到底怎么爬樓梯來(lái)聊一聊算法中的動(dòng)態(tài)規(guī)劃?。

面試真題

小明家有一樓梯共有10級(jí)臺(tái)階，每次可以爬1級(jí)或2級(jí)，問(wèn)小明爬到第10級(jí)臺(tái)階，一共有多少種走法？
> 為什么是“小明”呢？這是個(gè)奇怪的問(wèn)題~

真題分析

很多同學(xué)在第一次遇到這個(gè)爬樓梯的問(wèn)題可能會(huì)比較懵,不知道該如何來(lái)解決。我們首先需要做的就是尋找這個(gè)問(wèn)題的關(guān)鍵點(diǎn)：每次只能爬1級(jí)或2級(jí)。

遞歸思想

小明每次只能爬1級(jí)或2級(jí)，那么對(duì)于爬到第10級(jí)臺(tái)階來(lái)說(shuō)，最后一次操作為走1級(jí)（此時(shí)處于第9級(jí)臺(tái)階上）或走2級(jí)（此時(shí)處于第8級(jí)臺(tái)階上）。
假定我們有個(gè)表達(dá)式f可以來(lái)計(jì)算到達(dá)某階臺(tái)階的走法，那么對(duì)于第10階來(lái)說(shuō)，這個(gè)表達(dá)式就應(yīng)該為：f(10) = f(9) + f(8)。
> 對(duì)于這個(gè)表達(dá)式，是不是有種瞬間回到那初、高中的年代~

按如上規(guī)則，再次考慮，爬到第9級(jí)臺(tái)階時(shí)，最后一次操作為走1級(jí)（此時(shí)處于第8級(jí)臺(tái)階上）或走2級(jí)（此時(shí)處于第7級(jí)臺(tái)階上），此處的表達(dá)式為：f(9) = f(8) + f(7)。

…

依次處理，當(dāng)爬到第3級(jí)臺(tái)階時(shí)，計(jì)算的表達(dá)式就是f(3) = f(2) + f(1)。

那爬到第2級(jí)臺(tái)階有幾種方式呢：每次走1級(jí)或者一次走2級(jí)，也就是一共有2種走法，f(2) = 2。

爬到第1級(jí)臺(tái)階的方式肯定只有一種：走1級(jí)，f(1) = 1。

按我們的思考邏輯，相關(guān)代碼如下：

/** * @method climbStairs * @description 爬樓梯 * @param {number} n 樓梯臺(tái)階數(shù) * @return {number} 一共有多少種走法 */function climbStairs (n) { ?if (n === 1) { return 1 }; ?if (n === 2) { return 2 }; ?let num = 0; ?num = climbStairs(n - 1) + climbStairs(n - 2); ?return num;}// 調(diào)用函數(shù)，輸出結(jié)果let num = climbStairs(10);console.log(num); // 89

> Congratulations~我們已經(jīng)完成啦，得到了正確的結(jié)果。

就在你滿(mǎn)臉微笑、志得意滿(mǎn)的向面試官講解思路的時(shí)候，面試官十有八九會(huì)一副老狐貍得逞的樣子，繼續(xù)問(wèn)你，假如n的值比較大的，如40之類(lèi)的，上面定義的climbStairs的執(zhí)行性能如何。

我們來(lái)看下執(zhí)行的性能：

測(cè)試代碼如下：

console.time();let num = climbStairs(40);console.log(num);console.timeEnd()

我的mac配置如下：

MacBook Pro 處理器：2.5 GHz 四核Intel Core i7 內(nèi)存： 16GB

連續(xù)執(zhí)行三次數(shù)據(jù)如下：

序號(hào)結(jié)果執(zhí)行時(shí)間1165580141811.077ms2165580141817.025ms3165580141814.803ms

> 注：在執(zhí)行過(guò)程中有卡頓，不是瞬間輸出，如果執(zhí)行的是```climbStairs(100)```，你應(yīng)該會(huì)瞬間聽(tīng)到風(fēng)扇啟動(dòng)的嗚嗚聲

遞歸思想優(yōu)化

在上面代碼climbStairs的基礎(chǔ)上我們來(lái)進(jìn)行優(yōu)化處理。我們仔細(xì)分析代碼的執(zhí)行流程，就會(huì)發(fā)現(xiàn)有很多重復(fù)計(jì)算的地方，比如說(shuō)f(5)就會(huì)在f(6-1)、f(7-2)時(shí)被重復(fù)計(jì)算，這就浪費(fèi)了時(shí)間和性能。

那我們就選擇使用空間換時(shí)間的策略，設(shè)置對(duì)象numbers，保存爬到某級(jí)臺(tái)階的結(jié)果，避免重復(fù)計(jì)算，numbers對(duì)象的結(jié)果如下：

let numbers = { ?1: 1, ?2: 2 }

優(yōu)化后代碼如下：

/** * @method climbStairs * @description 爬樓梯 * @param {number} n 樓梯臺(tái)階數(shù) * @return {number} 一共有多少種走法 */function climbStairs (n) { ?// 存儲(chǔ)計(jì)算的結(jié)果，key(臺(tái)階) : num(走法) ?let numbers = { ? ?1: 1, ? ?2: 2 ?}; ?let tmpClimbStairs = function (n) { ? ?// 已存在的數(shù)據(jù)，直接返回，不再重新計(jì)算 ? ?if (numbers[n]) { ? ? ?return numbers[n]; ? ?} ? ?// 不存在的數(shù)據(jù)，進(jìn)行計(jì)算 ? ?let num = tmpClimbStairs(n - 1) + tmpClimbStairs(n - 2); ? ?// 計(jì)算完成后，存放如numbers中，下次可以直接使用 ? ?numbers[n] = num; ? ?// 返回結(jié)果 ? ?return num; ?} ?// 計(jì)算結(jié)果 ?let num = tmpClimbStairs(n); ?// 返回結(jié)果 ?return num;}

相同環(huán)境下，我們?cè)賮?lái)執(zhí)行測(cè)試，連續(xù)執(zhí)行三次數(shù)據(jù)如下：

序號(hào)結(jié)果執(zhí)行時(shí)間11655801417.100ms21655801417.478ms31655801416.260ms

> 消耗的時(shí)間竟然相差百倍之多，It’s amazing！說(shuō)明我們使用空間換時(shí)間的策略是正確的。

執(zhí)行結(jié)果幾乎是瞬間輸出的，執(zhí)行如絲襪奶茶般順滑~此時(shí)此刻你可以再次執(zhí)行climbStairs(100)來(lái)體驗(yàn)下絕對(duì)的性能飆升！

這道面試題處理成這樣已經(jīng)是非常OK的了，但是如果你已經(jīng)感到徹底滿(mǎn)足，為自己的聰明才智感到驕傲了，你就會(huì)聽(tīng)到面試官可愛(ài)（恨）的聲音傳來(lái)：”還有別的方法或性能更好的方法來(lái)實(shí)現(xiàn)嗎？“

是不是心中一口老血想噴出來(lái)面試官是不是故意的，是不是在針對(duì)我

哈哈，不慌不慌，小場(chǎng)面~

遞歸與遞推

遞歸與遞推是兩種不同的看待、分析問(wèn)題的思路。

遞歸：自頂向下的處理邏輯，有相應(yīng)的臨界點(diǎn)（終止遞歸的點(diǎn)）；

遞推：自底向上的處理邏輯，到達(dá)目標(biāo)點(diǎn)結(jié)束。

遞推思想

我們重新使用遞推的方式再來(lái)看這個(gè)問(wèn)題。

1. 爬到第1級(jí)臺(tái)階，有1種方式。?f(1) = 1；

2. 爬到第2級(jí)臺(tái)階，有2種方式：每次1級(jí)或1次2級(jí)。f(2) = 2；

3. 爬到第3級(jí)臺(tái)階的情況呢？

   不要忘了我們之前分析的關(guān)鍵點(diǎn)：每次只能1級(jí)或2級(jí)，
   對(duì)于第3級(jí)臺(tái)階來(lái)說(shuō)，可以是從第1級(jí)臺(tái)階出發(fā)也可以是從第2級(jí)臺(tái)階出發(fā)，
   所以f(3) = f(2) + f(1)

4. 同理可得爬到第4級(jí)臺(tái)階的情況，f(4) = f(3) + f(2)

我們得出一個(gè)結(jié)論：對(duì)于第N(N > 2)級(jí)臺(tái)階，其表達(dá)式為f(N) = f(N-1) + f(N-2)。那么我們?cè)诮Y(jié)算的過(guò)程中，每次都記錄下f(N-1)和f(N-2)的值，逐級(jí)遷移這個(gè)值，就可以得到f(N)了。

現(xiàn)在climbStairs代碼如下：

/** * @method climbStairs * @description 爬樓梯 * @param {number} n 樓梯臺(tái)階數(shù) * @return {number} 一共有多少種走法 */ function climbStair (n) { ?// 通過(guò)觀(guān)察，我們可只第1級(jí)和第2級(jí)都是返回對(duì)應(yīng)的n ?if (n <= 2) { ? ?return n; ?} else { ? ?// 對(duì)于n > 2的情況 ? ?let i = 1; ?// 初始存放第1級(jí)臺(tái)階的走法，對(duì)應(yīng)的是f(N-2) ? ?let j = 2; ?// 初始存放第2級(jí)臺(tái)階的走法，對(duì)應(yīng)的是f(N-1); ? ?// 定義走法num ? ?let num; ? ?// 從第3級(jí)開(kāi)始，執(zhí)行循環(huán)操作 ? ?for (let k = 3; k <= n; k++) { ? ? ?// f(N) = f(N-1) + f(N-2) ? ? ?num = i + j; ? ? ?// 同時(shí)移動(dòng) ? ? ?// 將f(N-1)的值給f(N-2) ? ? ?i = j; ? ? ?// 將當(dāng)前值給f(N-1) ? ? ?j = num; ? ?} ? ?// 返回結(jié)果 ? ?return num; ?} }

> 這一次我們直接在時(shí)間復(fù)雜度上降低了，變成了O(N),執(zhí)行起來(lái)更加是和那啥一樣，流暢、順滑~

我們來(lái)看下測(cè)試效果，連續(xù)執(zhí)行三次測(cè)試結(jié)果如下：

序號(hào)結(jié)果執(zhí)行時(shí)間11655801416.570ms21655801416.647ms31655801416.658ms

> 相對(duì)于遞歸的實(shí)現(xiàn)方式，遞推的實(shí)現(xiàn)從時(shí)間復(fù)雜度上更低，執(zhí)行也會(huì)更高效~

此時(shí)此刻，這個(gè)爬樓梯的問(wèn)題終于是回答圓滿(mǎn)了，這個(gè)時(shí)候面試官看你就會(huì)像丈母娘看女婿一樣，怎么看怎么可愛(ài)。

動(dòng)態(tài)規(guī)劃的算法問(wèn)題有很多種不同的形式，爬樓梯是其中的一種。

作者：胡哥有話(huà)說(shuō)
鏈接：https://www.imooc.com/article/315121
來(lái)源：慕課網(wǎng)
本文原創(chuàng)發(fā)布于慕課網(wǎng) ，轉(zhuǎn)載請(qǐng)注明出處，謝謝合作