【算法】爬楼梯(JavaScript实现)

有一个楼梯，你一次只能往上走一阶或者两阶。请编写函数 climbStairs，它接受一个整数 n 作为参数，表示这个楼梯有多少阶。请你返回一个整数，表示这个楼梯一共有多少种走法。例如：

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

不难发现这道题思想其实是斐波那契数列

F(1)=1，F(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) 

如果直接用不作处理的递归求解的话，很明显是不可取的，但次数多时，调用的次数太多将导致时间超时。

仔细观察一下，n > 2时，每一次的结果都可以根据前两次的结果得出，因此递推的思想出来了，我们可以用递推求解。

const climbStairs = (n) => {
  // 用一个数组保存每一次的结果
  let arr = new Array(n)
  for(let i = 1; i <= n; i++) {
    if(i < 3) {
      arr[i - 1] = i
    } else {
      // 逐一递推得到结果
      arr[i - 1] = arr[i - 2] + arr[i - 3]
    }
  }
  return n <= 0 ? 0 : arr[n - 1]
}