记字节前端面试一道简单的算法题

70. 爬楼梯 （medium）

方法1.动态规划

• 思路：因为每次可以爬 1 或 2 个台阶，所以到第n阶台阶可以从第n-2或n-1上来，其实就是斐波那契的dp方程
• 复杂度分析：时间复杂度O(n)，空间复杂度O(1)

Js:

代码语言：javascript复制

var climbStairs = function (n) {
    const memo = [];
    memo[1] = 1;
    memo[2] = 2;
    for (let i = 3; i <= n; i  ) {
        memo[i] = memo[i - 2]   memo[i - 1];//所以到第n阶台阶可以从第n-2或n-1上来
    }
    return memo[n];
};

//状态压缩
var climbStairs = (n) => {
    let prev = 1;
    let cur = 1;
    for (let i = 2; i < n   1; i  ) {
        [prev, cur] = [cur, prev   cur]
        // const temp = cur;   // 暂存上一次的cur
        // cur = prev   cur;   // 当前的cur = 上上次cur   上一次cur
        // prev = temp;        // prev 更新为 上一次的cur
    }
    return cur;
}

Java:

代码语言：javascript复制

class Solution {
    public int climbStairs(int n) {
        int prev = 1, cur = 1;
        for (int i = 2; i < n   1; i  ) {
        int temp = cur;
        cur = prev   cur;  
        prev = temp; 
        }
        return cur;
    }
}

视频讲解（高效学习）:点击学习

腾讯广告算法大赛

0 人点赞