题目：https://leetcode-cn.com/problems/climbing-stairs/

image.png

思路：有一个很重要的点就是楼梯一次可以爬 1 或 2 个台阶。假设有6个台阶，那么最后一步可以是在第4个台阶上到第6个台阶，也可以是从第5个台阶上到第6个台阶。所以上到第6个台阶的方法数，无非就是上第4个台阶的方法数加上第5个台阶的方法。所以依次推断可以得出70. 爬楼梯 - 图2，所以其实就是斐波那契数列。

方法一：斐波那契数列

  1. /**
  2.  * @param {number} n
  3.  * @return {number}
  4.  */
  5. var climbStairs = function(n) {
  6.     let tmp1 = 0
  7.     let tmp2 = 1
  9.     for (let i = 0; i < n; i++) {
  10.         [tmp2, tmp1] = [tmp1 + tmp2, tmp2]
  11.     }
  13.     return tmp2
  14. };

复杂度分析：

  • 时间复杂度：70. 爬楼梯 - 图3
  • 空间复杂度：70. 爬楼梯 - 图4