题目描述：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例1:

1
2
3
4
5
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例2:

1
2
3
4
5
6
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

题解方法一：逐位查找

解题思路
设跳上 n 级台阶有 f(n) 种跳法。在所有跳法中，青蛙的最后一步只有两种情况： 跳上 1 级或 2 级台阶。

  • 当为 1 级台阶： 剩 n−1 个台阶，此情况共有 f(n−1) 种跳法。

  • 当为 2 级台阶： 剩 n−2 个台阶，此情况共有 f(n−2) 种跳法。
    即 f(n)f(n)f(n) 为以上两种情况之和，即 f(n)=f(n−1)+f(n−2)f(n)=f(n-1)+f(n-2)f(n)=f(n−1)+f(n−2) ，以上递推性质为斐波那契数列。因此，本题可转化为 求斐波那契数列的第 nnn 项，区别仅在于初始值不同：

  • 青蛙跳台阶问题： f(0)=1 , f(1)=1 , f(2)=2 。

  • 斐波那契数列问题： f(0)=0 , f(1)=1 , f(2)=1 。

动态规划解析：
状态定义： 设 dp 为一维数组，其中 dp[i] 的值代表斐波那契数列的第 i 个数字。
转移方程： dp[i+1]=dp[i]+dp[i−1],即对应数列定义 f(n+1)=f(n)+f(n−1) 。
初始状态： dp[0]=1 , dp[1]=1 ，即初始化前两个数字。
返回值： dp[n] ，即斐波那契数列的第 n 个数字。

状态压缩：
若新建长度为 n 的 dp 列表，则空间复杂度为 O(N)。

由于 dp 列表第 i 项只与第 i−1 和第 i−2 项有关，因此只需要初始化三个整形变量 sum, a, b ，利用辅助变量 sum 使 a,b 两数字交替前进即可 （具体实现见代码） 。由于省去了 dp 列表空间，因此空间复杂度降至 O(1)。

代码实现如下：

1
2
3
4
5
6
7
8
9
function climbStairs(n) {
  let a = 1, b = 1;
  // a = f(0), b = f(1) 
  // n = 2 则 n-1= 1 一次循环， f(2) = a +b = f(0) + f(1)
  for (let i = 0; i < n - 1; i++) {
    [a, b] = [b, a + b];
  }
  return b;
}

总结：大功告成✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️

参考链接: