70-ClimbingStairs.md

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提示：

• 1 <= n <= 45

思路：

动态规划，自底而上思考

这个函数使用了动态规划的思想，通过迭代的方式计算出爬到第n个台阶的方法数。下面是这个函数的逻辑分析：

1. 函数climbStairs接收一个参数n，表示台阶的总数。
2. 初始化两个变量a和b，都为1。在这里，a代表爬到第1个台阶的方法数，b代表爬到第2个台阶的方法数。因为爬到第1个台阶只有1种方法（直接一步上去），而爬到第2个台阶有两种方法（一步一台阶或两步直接上去）。
3. 使用while循环，循环条件是n-- > 0，意味着从第3个台阶开始，一直到第n个台阶。每次循环，n减1，直到n变为0。
4. 在循环体内，首先执行b += a，这一步是关键，它表示到达当前台阶的方法数是前两个台阶方法数之和。这是因为到达当前台阶的方法可以通过最后一步从上一个台阶（方法数为a）或者从上上一个台阶（方法数为b）到达。
5. 接着执行a = b - a，这一步更新a的值，使其成为下一次循环中b的旧值。这样做是为了在下一次迭代时，b能够正确地加上新的a值。
6. 循环结束后，返回a的值，此时a代表爬到第n个台阶的方法数。

这个函数利用了斐波那契数列的性质，即每个数字是前两个数字的和，来解决爬楼梯问题。这种方法的时间复杂度是O(n)，空间复杂度是O(1)，因为它只需要常数级的额外空间。

/**
 * @param {number} n
 * @return {number}
 */
const climbStairs = n => {
  let a = 1,
    b = 1;
  while (n-- > 0) {
    b += a;
    a = b - a;
  }
  return a;
};