脚本宝典收集整理的这篇文章主要介绍了记字节前端面试一道简单的算法题，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

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

70. 爬楼梯 （medium）

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶

方法1.动态规划

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

Js:

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:

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;
    }
}

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

目录：

1.开篇介绍

2.时间空间复杂度

3.动态规划

4.贪心

5.二分查找

6.深度优先&广度优先

7.双指针

8.滑动窗口

9.位运算

10.递归&分治

11剪枝&回溯

12.堆

13.单调栈

14.排序算法

15.链表

16.set&map

17.栈

18.队列

19.数组

20.字符串

21.树

22.字典树

23.并查集

24.其他类型题

脚本宝典总结

以上是脚本宝典为你收集整理的记字节前端面试一道简单的算法题全部内容，希望文章能够帮你解决记字节前端面试一道简单的算法题所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。