面試官在“逗”你系列：到底應該怎么爬樓梯？！

直奔主題

演算法題是在面試程序中考察候選人邏輯思維能力、手寫代碼能力的一種方式，因為有一句古話說的好：“說一千道一萬，不如寫段代碼看一看”，

今天我們就來個單刀直入，直奔主題，從一個真實面試題到底怎么爬樓梯來聊一聊演算法中的動態規劃 ，

面試真題

小明家有一樓梯共有10級臺階，每次可以爬1級或2級，問小明爬到第10級臺階，一共有多少種走法？

為什么是“小明”呢？這是個奇怪的問題~

真題分析

很多同學在第一次遇到這個爬樓梯的問題可能會比較懵,不知道該如何來解決，我們首先需要做的就是尋找這個問題的關鍵點：每次只能爬1級或2級，

遞回思想

小明每次只能爬1級或2級，那么對于爬到第10級臺階來說，最后一次操作為走1級（此時處于第9級臺階上）或走2級（此時處于第8級臺階上），
假定我們有個運算式f可以來計算到達某階臺階的走法，那么對于第10階來說，這個運算式就應該為：f(10) = f(9) + f(8)，

對于這個運算式，是不是有種瞬間回到那初、高中的年代~

按如上規則，再次考慮，爬到第9級臺階時，最后一次操作為走1級（此時處于第8級臺階上）或走2級（此時處于第7級臺階上），此處的運算式為：f(9) = f(8) + f(7)，

......

依次處理，當爬到第3級臺階時，計算的運算式就是f(3) = f(2) + f(1)，

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

爬到第1級臺階的方式肯定只有一種：走1級，f(1) = 1，

按我們的思考邏輯，相關代碼如下：

/**
 * @method climbStairs
 * @description 爬樓梯
 * @param {number} n 樓梯臺階數
 * @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;
}

// 呼叫函式，輸出結果
let num = climbStairs(10);
console.log(num); // 89

Congratulations~我們已經完成啦，得到了正確的結果，

就在你滿臉微笑、志得意滿的向面試官講解思路的時候，面試官十有八九會一副老狐貍得逞的樣子，繼續問你，假如n的值比較大的，如40之類的，上面定義的climbStairs的執行性能如何，

我們來看下執行的性能：

測驗代碼如下：

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

我的mac配置如下：

MacBook Pro 
處理器：2.5 GHz 四核Intel Core i7
記憶體： 16GB

連續執行三次資料如下：

注：在執行程序中有卡頓，不是瞬間輸出_{，如果執行的是```climbStairs(100)```，你應該會瞬間聽到風扇啟動的嗚嗚聲}

遞回思想優化

在上面代碼climbStairs的基礎上我們來進行優化處理，我們仔細分析代碼的執行流程，就會發現有很多重復計算的地方，比如說f(5)就會在f(6-1)、f(7-2)時被重復計算，這就浪費了時間和性能，

那我們就選擇使用空間換時間的策略，設定物件numbers，保存爬到某級臺階的結果，避免重復計算，numbers物件的結果如下：

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

優化后代碼如下：

/**
 * @method climbStairs
 * @description 爬樓梯
 * @param {number} n 樓梯臺階數
 * @return {number} 一共有多少種走法
*/
function climbStairs (n) {
  // 存盤計算的結果，key(臺階) : num(走法)
  let numbers = {
    1: 1,
    2: 2
  };

  let tmpClimbStairs = function (n) {
    // 已存在的資料，直接回傳，不再重新計算
    if (numbers[n]) {
      return numbers[n];
    }

    // 不存在的資料，進行計算
    let num = tmpClimbStairs(n - 1) + tmpClimbStairs(n - 2);
    // 計算完成后，存放如numbers中，下次可以直接使用
    numbers[n] = num;

    // 回傳結果
    return num;
  }

  // 計算結果
  let num = tmpClimbStairs(n);
  // 回傳結果
  return num;
}

相同環境下，我們再來執行測驗，連續執行三次資料如下：

消耗的時間竟然相差百倍之多，It's amazing！說明我們使用空間換時間的策略是正確的，

執行結果幾乎是瞬間輸出的，執行如絲襪奶茶般順滑~此時此刻你可以再次執行climbStairs(100)來體驗下絕對的性能飆升！

這道面試題處理成這樣已經是非常OK的了，但是如果你已經感到徹底滿足，為自己的聰明才智感到驕傲了，你就會聽到面試官可愛（恨）的聲音傳來：”還有別的方法或性能更好的方法來實作嗎？“

是不是心中一口老血想噴出來_{面試官是不是故意的，是不是在針對我}

哈哈，不慌不慌，小場面~

遞回與遞推

遞回與遞推是兩種不同的看待、分析問題的思路，

遞回：自頂向下的處理邏輯，有相應的臨界點（終止遞回的點）；

遞推：自底向上的處理邏輯，到達目標點結束，

遞推思想

我們重新使用遞推的方式再來看這個問題，

1. 爬到第1級臺階，有1種方式， f(1) = 1；

2. 爬到第2級臺階，有2種方式：每次1級或1次2級，f(2) = 2；

3. 爬到第3級臺階的情況呢？

   不要忘了我們之前分析的關鍵點：每次只能1級或2級，
   對于第3級臺階來說，可以是從第1級臺階出發也可以是從第2級臺階出發，
   所以f(3) = f(2) + f(1)

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

我們得出一個結論：對于第N(N > 2)級臺階，其運算式為f(N) = f(N-1) + f(N-2)，那么我們在結算的程序中，每次都記錄下f(N-1)和f(N-2)的值，逐級遷移這個值，就可以得到f(N)了，

現在climbStairs代碼如下：

/**
 * @method climbStairs
 * @description 爬樓梯
 * @param {number} n 樓梯臺階數
 * @return {number} 一共有多少種走法
*/
function climbStair (n) {
  // 通過觀察，我們可只第1級和第2級都是回傳對應的n
  if (n <= 2) {
    return n;
  } else {
    // 對于n > 2的情況
    let i = 1;  // 初始存放第1級臺階的走法，對應的是f(N-2)
    let j = 2;  // 初始存放第2級臺階的走法，對應的是f(N-1);

    // 定義走法num
    let num;

    // 從第3級開始，執行回圈操作
    for (let k = 3; k <= n; k++) {
      // f(N) = f(N-1) + f(N-2)
      num = i + j;

      // 同時移動
      // 將f(N-1)的值給f(N-2)
      i = j;
      // 將當前值給f(N-1)
      j = num;
    }
    // 回傳結果
    return num;
  }
}

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

我們來看下測驗效果，連續執行三次測驗結果如下：

相對于遞回的實作方式，遞推的實作從時間復雜度上更低，執行也會更高效~

此時此刻，這個爬樓梯的問題終于是回答圓滿了，這個時候面試官看你就會像丈母娘看女婿一樣，怎么看怎么可愛，

動態規劃的演算法問題有很多種不同的形式，爬樓梯是其中的一種，在這里胡哥要給大家留一道面試題啦，看看大家對動態規劃是不是有了深刻的理解，

面試真題如下：

你是一個有信仰的強盜，有一排房屋等待你去搶劫，在搶劫中不能相鄰的房屋不能搶，只能間隔一個或多個房屋進行搶劫，房屋中錢財都是非負整數，資料格式如下：[3, 4, 5, 2, 1, 1]，請計算出你能搶到的最大金額是多少，

這個強盜相當有信仰，竟然不都搶走~

歡迎各位小伙伴留言，談談你對動態規劃的理解，留下這道面試題的答案，一起來探討交流~

后記

以上就是胡哥今天給大家分享的內容，喜歡的小伙伴記得點贊、收藏呦，關注胡哥有話說，學習前端不迷路，歡迎多多留言交流...

胡哥有話說，專注于大前端技術領域，分享前端系統架構，框架實作原理，最新最高效的技術實踐！

標籤：JavaScript

上一篇：使用Markdown來豐富Discord對話效果

下一篇：JavaScript事件處理