Loading...
墨滴

Shinkai005

2021/12/13  阅读:72  主题:红绯

leetcode】70.爬楼梯

【leetcode】70.爬楼梯

题目描述

image-20211212223119541
image-20211212223119541

题目思路

爬到第N个台阶可以在第N-1个台阶爬一个台阶,或者N-2个台阶爬两个台阶

F(n) = F(n-1) + F(n-2);

可以使用动态规划

解释一下, 问的是方法,那么是不是爬到n-1级台阶的方法 + 爬到n-2级的方法就是n的方法?,从n开始迭代到0 即可

算了解释更详细一些

  1. 爬到第1级 1种 爬到2级 0-2 0-1-2 两种
  2. 爬到3呢? 爬到1级+爬到2级 === 爬到n-2+爬到n-1 == 3种 0-1-3 0-1-2-3 0-2-3
  3. 解释一下上面方法, 爬到3级的方法就是 爬到2级和爬到1级方法的和
    1. 因为n-2到n方法只有爬两级
    2. n-1到n的方法只有爬1级
  4. ok? F(n) = F(n-1) + F(n-2);

某人说我敷衍! 感觉认真的点个赞 在看 谢谢!

个人题解

/**
 * @param {number} n
 * @return {number}
 */

var climbStairs = function (n{
    // dp[i] 为第 i 阶楼梯有多少种方法爬到楼顶
    // dp[i] = dp[i - 1] + dp[i - 2]
    let dp = [12]
    for (let i = 2; i < n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n - 1];
};

总结优化

这块是不需要单独写 n<2情况的, 最后结果是符合n<2情况,因此不需要单独写出来高中数学吧.

可以优化空间复杂度, 不用数组去存dp

/**
 * @param {number} n
 * @return {number}
 */

var climbStairs = function (n{
    // dp[i] 为第 i 阶楼梯有多少种方法爬到楼顶
    // dp[i] = dp[i - 1] + dp[i - 2]
    if(n===1)return 1;
    let dp0 = 1;
    let dp1 = 2;
    for (let i = 2; i < n; i++) {
        const temp = dp0;
        dp0 = dp1;
        dp1 = dp1 +temp;
    }
    return dp1;
};

时间复杂度(time complexity)

O(n)

空间复杂度(space complexity)

O(n)优化前,数组不断地变大. 但是其实不需要记录,只需要最终的结果因此,不断地修改dp1值就好

优化后O(1)

Shinkai005

2021/12/13  阅读:72  主题:红绯

作者介绍

Shinkai005