[!info] related notes 算法面试题型 MOC 动态规划

爬楼梯

题目

LeetCode 70：每次爬 1 或 2 阶，求到达第 n 阶的不同顺序方案数。题目输入为 1 ≤ n ≤ 45。

题解

dp[i] 表示到达第 i 阶的方案数。最后一步只能来自 i - 1 或 i - 2，因此 dp[i] = dp[i - 1] + dp[i - 2]。dp[0] = 1 是空路径的计数基准；它不表示原题要求输入 0。

var climbStairs = function(n) {
    const dp = new Array(n+1).fill(0);
    dp[0] = 1
    dp[1] = 1;
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n]
};

时间 O(n)，空间 O(n)；只保留前两个状态可降至 O(1) 空间。这里计数顺序方案，例如 1+2 与 2+1 是两种，不是零钱兑换 II 的无序组合。