LeetCode 之 JavaScript 解答第70题 —— 爬楼梯（Climbing Stair

chemzqm 发布于2019-08-23 16:55 / 1508人阅读

摘要：小鹿题目假设你正在爬楼梯。需要阶你才能到达楼顶。你有多少种不同的方法可以爬到楼顶呢注意给定是一个正整数。算法思路二种解决思路，第一利用递归第二利用动态规划。就是因为有了重复元素的计算，导致了时间复杂度成指数的增长。

Time：2019/4/12
Title:Clibing Srairs
Difficulty: Easy
Author:小鹿

题目：Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

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

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

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

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

slove ▉ 算法思路

二种解决思路，第一利用递归；第二利用动态规划。

1）递归的实现方式：

首先，我们要知道递归使用应该满足的三个条件，之前在前边的题型中讲到过，后边我会整理成系列文章供大家方便学习。然后按照我们之前讲过的方式去写出递归公式，然后转化为递归的代码。我们会发现递归的时间复杂度为 O（2^n），我们是否还记得递归的缺点有一条就是警惕递归重复元素计算。就是因为有了重复元素的计算，导致了时间复杂度成指数的增长。

为了能够降低时间复杂度，我们可以用散列表来记录重复元素记录过的值，但是需要申请额外的空间进行存储，导致空间复杂度为O(n)，时间复杂度降为O(n)，也正是利用了空间换时间的思想。

2）动态规划的实现方式：

我们可以仔细发现上方的递归的方式还是可以优化的，我们换种方式去思考，从底向上去思考，其实我们计算一个值之存储之前的两个值就可以了（比如：计算 f(6) ,需要知道 f(5) 和 f(4) 的值就可以了），我们可以不用存储之前的值，此时可以将空间复杂度降为 O(1)。

▉ 代码实现（递归）

优化后的递归实现。

//递归实现
//时间复杂度为 O(n)，空间复杂度为 O(n)
var climbStairs = function(n) {
    let map = new Map();
    if(n === 1) return 1;
    if(n === 2) return 2;
    if(map.has(n)){
        return map.get(n);
    }else{
        let value = climbStairs(n - 1) +climbStairs(n - 2);
        map.set(n,value);
        return value;
    }
};

▉ 代码实现（动态规划）

//动态规划
//时间复杂度为O(n) 空间复杂度为O(1)
var climbStairs = function(n) {
    if(n < 1) return 0;
    if(n === 1) return 1;
    if(n === 2) return 2;

    let a = 1;
    let b = 2;
    let temp = 0;

    for (let i = 3; i < n + 1; i++) {
        temp = a + b;
        a = b;
        b = temp;          
    }
    return temp;
}

欢迎一起加入到 LeetCode 开源 Github 仓库，可以向 me 提交您其他语言的代码。在仓库上坚持和小伙伴们一起打卡，共同完善我们的开源小仓库！
Github：https://github.com/luxiangqia...

云服务器 GPU云服务器爬楼梯 javascript算法题汇编语言程序设计第二版课后题答案 javascript必问面试题

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/103522.html

leetcode70 climbing stairs 爬楼梯游戏

摘要：题目要求假设有级台阶为正整数，每次可以爬一级台阶或两级台阶。问有多少种方法爬完级台阶递归方法最后一步可以是一级台阶，或者是两级台阶，一共两种情况。题目要求：假设有n级台阶（n为正整数），每次可以爬一级台阶或两级台阶。问有多少种方法爬完n级台阶？递归方法最后一步可以是一级台阶，或者是两级台阶，一共两种情况。可通过递归获得n-1级台阶和n-2级台阶的和获得n级台阶的结果台阶数量过高的话...

姘存按 2019-08-14 17:52 评论0 收藏0
[Leetcode] Climbing Stairs 爬楼梯

摘要：递归法复杂度时间空间思路这题几乎就是求解斐波那契数列。最简单的方法就是递归。但重复计算时间复杂度高。代码递推法复杂度时间空间思路实际上我们求的时候只需要和的值，所以可以减少一些空间啊。 Climbing Stairs You are climbing a stair case. It takes n steps to reach to the top. Each time you c...

tinyq 2019-08-14 12:26 评论0 收藏0
[leetcode] Climbing Stairs

摘要：实质就是把之前出现过的中间结果记录，下次再出现相同情况的时候，通过可以只用的时间复杂度得到。表示到达第层楼梯的不同走法。那么题目中每次可以选择走一步，或者两步，。从迭代公式可以知道，有两个，和。 70. Climbing Stairs You are climbing a staircase. It takes n steps to reach to the top.Each tim...

int64 2019-08-14 16:50 评论0 收藏0
【Leetcode】70. 爬楼梯

摘要：题目假设你正在爬楼梯。需要阶你才能到达楼顶。你有多少种不同的方法可以爬到楼顶呢注意给定是一个正整数。示例输入输出解释有两种方法可以爬到楼顶。阶阶阶阶阶阶阶题解这个题目只要模拟一下基本就能想到是，状态方程写出来就是斐波那契数列。题目假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。示...

raoyi 2019-07-24 10:49 评论0 收藏0