博客

爬楼梯

• https://leetcode.cn/problems/climbing-stairs/

描述

• 假设你正在爬楼梯。需要 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

算法实现

1 ）方案 1

function climbStairs(n: number): number {
    // n为1的情况
    if(n < 2) {
        return 1
    }
    let dp: number[] = [1,1]; // 初始化工具
    for(let i:number = 2; i <= n; ++ i) {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}

• 思路
  • 爬到第n阶可以在n-1阶爬1个台阶，或在n-2阶爬两个台阶
  • F(n) = F(n-1) + F(n-2)
    • F(n) 代表n个台阶一共有多少种方法爬上去
    • 爬到第n阶方法数量 = 爬到n-1阶方法数量 + 爬到n-2阶方法数量
  • 一个问题可以分解为两个相互重叠的子问题，用动态规划解题
• 步骤
  • 定义子问题：F(n) = F(n-1) + F(n-2)
  • 反复执行子问题：从2 ~ n, 执行上述公式
  • 这里的2，必须保证n-2是正的，如果只有1个台阶只有一个方法，而且1-2=-1,台阶数量不能为负数
• 注意
  • dp 数组用来记录，第n阶需要多少种方法，下标为0的位置(0阶，当然n不能为0)设置成1
  • 下标为1的位置，1阶是1，为什么把下标为0的位置设置1，因为它能帮助方便求得2阶，真实情况下n不会等于0，此处需要的是工具值

2 ）方案 2

function climbStairs(n: number): number {
    // n为1的情况
    if(n < 2) {
        return 1;
    }
    
    // 用两个变量来代表前两步
    let dp0 = 1;
    let dp1 = 1;

    for(let i: number = 2; i <= n; ++ i) {
        // 不断地把dp0, dp1分别代表数组的倒数两个数字
        let tmp = dp0;
        dp0 = dp1;
        dp1 += tmp; // 用常量取代数组，空间复杂度下降
    }
    return dp1;
}

• 思路同上，优化了空间复杂度，官方给的滚动数组初始化的一些变量不太好理解，后面的矩阵快速幂方法比较复杂了，通项公式法就是用的数学推导