爬楼梯 ​

假设你正在爬楼梯。需要 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 层最终都是只有 n-1层+1步 + n-2层+2步 这两种爬楼梯的方式

• 爬 2 阶到楼顶的方法有(2 种): 1+1 || 2
• 爬 3 阶到楼顶的方法有(3 种): 1+1+1 || 1+2 || 2+1
  • 解析: 先爬 1 阶(1),1 到 3 有两阶也就是 2 种方法(1+1+1 1+2) 先爬 2 阶(1+1 2),2 到 3 阶有一种方法(1+1+1(重复了不记录次数) 2+1)
• 爬 4 阶到楼顶的方法有(5 种): 1+1+1+1 || 1+2+1 || 2+1+1 || 1+1+2 || 2+2
  • 解析:
  • 先爬 3 阶(3 种方法)这 3 种方法+1 都能到第 4 阶(1+1+1+1 || 1+2+1 || 2+1+1), 所以这里爬到 4 阶有 3 种方法
  • 先爬 2 阶(2 种方法)这 2 种方法+2 都能到 4 阶(1+1+2 || 2+2),其中把 2 分解成 1+1 还会多一种 1+1+1+1(重复了不记录次数) 所以这里爬到 4 阶有 2 种方法
  • 3 + 2 = 5
• 爬 5 阶到楼顶的方法有(8 种): (第 4 阶 + 1) + (第 3 阶 + 2)
• 爬 6 阶到楼顶的方法有(8 种): (第 6 阶 - 1) + (第 6 阶 - 2)
• 爬 n 阶到楼顶的方法有: (第 n-1 阶) + (第 n-2 阶)

递归 ​

// 可能执行超时
function climbStairs(n: number): number {
    if (n <= 3) return n;
    return climbStairs(n-1) + climbStairs(n-2)
};

计数 ​

从 1 阶开始记录所有阶数有几种方法, n 阶 = (n-1)的方法数量 + (n-2)的方法数量

function climbStairs(n: number): number {
    let arr = [];
    arr[1] = 1;
    arr[2] = 2;
    for (let i = 3; i <= n; i++) {
      arr[i] = arr[i-1] + arr[i-2];
    }
    return arr[n];
};