LeetCode | 70. 爬楼梯

[aermin]

题目

题解

动态规划

思路及代码

/**
 * @param {number} n
 * @return {number}
 */
/**
 * 如果最后一步如果是跨一个台阶，那方案数就是前一个台阶有的方案数f(x-1)；
 * 如果最后一步如果是跨两个台阶，那方案数就是前两个台阶有的方案数f(x-2)；
 * 两种情况加起来就是x级台阶的方案数。
 * 转移方程：f(x)=f(x−1)+f(x−2)
 * 可以用数组存下每级台阶的方案数，空间复杂度O(n), 用滚动数组思想，空间复杂度优化成O(1)
 */
var climbStairs = function(n) {
    // 用数组存下每级台阶的方案数，空间复杂度O(n)
    // const dp = [];
    // dp[1] = 1;
    // dp[2] = 2;
    // for(let i = 3; i <= n; i++) {
    //     dp[i] = dp[i - 1] + dp[i - 2];
    // }
    // return dp[n];

    // 用滚动数组思想，空间复杂度优化成O(1)
    let prePre = 0, pre = 0, cur = 1;
    for(let i = 0; i < n; i++) {
        prePre = pre;
        pre = cur;
        cur = prePre + pre;
    }
    return cur;
};

复杂度分析

时间复杂度：循环执行 n次，每次花费常数的时间代价，故渐进时间复杂度为 O(n)。
空间复杂度：这里只用了常数个变量作为辅助空间，故渐进空间复杂度为 O(1)。

图解：

• 用数组存下每级台阶的方案数，空间复杂度O(n)

• 用滚动数组思想，空间复杂度优化成O(1):

Refence

爬楼梯 作者：LeetCode-Solution
画解算法：70. 爬楼梯 作者：灵魂画手