fat-cat

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

输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。1. 1 阶 + 1 阶； 2. 2 阶

n = 1，1 种方法 n = 2, 2 种方案 n = 3， 3 种方法

• 1 + 1 + 1
• 1 + 2
• 2 + 1

n = 4， 5 种方法

• 1 + 1 + 1 + 1
• 1 + 1 + 2
• 1 + 2 + 1
• 2 + 1 + 1
• 2 + 2

解题步骤

• 确定 dp[i]：爬到第 i 阶楼梯有 dp[i] 种方法
• 确定递推公式： dp[i] = dp[i - 1] + dp[i - 2]
• 初始化 dp 数组，dp[0] = 0, dp[1] = 1, dp[2] = 2, 从 i=3， 开始递推
• 确定递推顺序：从前向后
• 举例推导 dp 数组: dp[1] = 1, dp[2] = 2, dp[3] = 3, dp[4] = 5

解题思路：可以这样想，n 个台阶，一开始可以爬 1 步，也可以爬 2 步，那么 n 个台阶爬楼的爬楼方法就等于 一开始爬 1 步的方法数 + 一开始爬 2 步的方法数，这样我们就只需要计算 n-1 个台阶的方法数和 n-2 个台阶方法数，同理，计算 n-1 个台阶的方法数只需要计算一下 n-2 个台阶和 n-3 个台阶，计算 n-2 个台阶需要计算一下 n-3 个台阶和 n-4 个台阶……

    const climbStairs = (n) => {
        if(n === 1) return 1

        let sum = [1, 1, 2]

        for(let i = 3; i <= n; i++){
            sum[i] = sum[i - 1] + sum[i - 2]
        }

        return sum[n]
    }

    console.log(climbStairs(5)) // 8