有一個(gè)樓梯，你一次只能往上走一階或者兩階。請編寫函數(shù) climbStairs，它接受一個(gè)整數(shù) n 作為參數(shù)，表示這個(gè)樓梯有多少階。請你返回一個(gè)整數(shù)，表示這個(gè)樓梯一共有多少種走法。例如：

climbStairs(1) // => 1
climbStairs(2) // => 2
climbStairs(3) // => 3
climbStairs(10) // => 89

不難發(fā)現(xiàn)這道題思想其實(shí)是斐波那契數(shù)列

F(1)=1，F(xiàn)(1)=2, F(n)=F(n-1)+F(n-2)（n>2，n∈N*）

因此我們可以直接用遞歸求解：

const climbStairs = (n) => n < 3 ? n : climbStairs(n-1) + climbStairs(n-2) 

如果直接用不作處理的遞歸求解的話，很明顯是不可取的，但次數(shù)多時(shí)，調(diào)用的次數(shù)太多將導(dǎo)致時(shí)間超時(shí)。

仔細(xì)觀察一下，n > 2時(shí)，每一次的結(jié)果都可以根據(jù)前兩次的結(jié)果得出，因此遞推的思想出來了，我們可以用遞推求解。

const climbStairs = (n) => {
  // 用一個(gè)數(shù)組保存每一次的結(jié)果
  let arr = new Array(n)
  for(let i = 1; i <= n; i++) {
    if(i < 3) {
      arr[i - 1] = i
    } else {
      // 逐一遞推得到結(jié)果
      arr[i - 1] = arr[i - 2] + arr[i - 3]
    }
  }
  return n <= 0 ? 0 : arr[n - 1]
}