[Leetcode] Climbing Stairs 爬楼梯

tinyq 发布于2019-08-14 12:26 / 1490人阅读

摘要：递归法复杂度时间空间思路这题几乎就是求解斐波那契数列。最简单的方法就是递归。但重复计算时间复杂度高。代码递推法复杂度时间空间思路实际上我们求的时候只需要和的值，所以可以减少一些空间啊。

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?

递归法 复杂度

时间 O(1.618^N) 空间 O(N)

思路

这题几乎就是求解斐波那契数列。最简单的方法就是递归。但重复计算时间复杂度高。

代码

public class Solution {
    public int climbStairs(int n) {
        if(n==1 || n==0) return 1;
        else return climbStairs(n-1) + climbStairs(n-2);
    }
}

动态规划 复杂度

时间 O(N) 空间 O(N)

思路

将之前计算过的结果存下来，节省了一些时间。

代码

public class Solution {
    public int climbStairs(int n) {
        if(n==0) return 0;
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
}

递推法 Recurrance 复杂度

时间 O(N) 空间 O(1)

思路

实际上我们求n的时候只需要n-1和n-2的值，所以可以减少一些空间啊。

代码

public class Solution {
    public int climbStairs(int n) {
        int[] f = new int[]{0,1,2};
        if(n < 3) return f[n];
        for(int i = 2; i < n; i++){
            f[0] = f[1];
            f[1] = f[2];
            f[2] = f[0] + f[1];
        }
        return f[2];
    }
}

矩阵法 复杂度

时间 O(logN) 空间 O(1)

专线服务服务器托管爬楼梯 Climbing Stairs LeetCode

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

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

leetcode70 climbing stairs 爬楼梯游戏

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

姘存按 2019-08-14 17:52 评论0 收藏0
LeetCode 之 JavaScript 解答第70题 —— 爬楼梯（Climbing Stair

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

chemzqm 2019-08-23 16:55 评论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

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
leetcode 746 Min Cost Climbing Stairs

摘要：同时你可以选择从第阶开始或者第一阶开始。我们的目标是找出你爬到最顶层所付出的最小的开销。最低开销是，从第阶开始，只花费就可以到顶层。想法动态规划问题。的长度应该为数组长度加一，其中数组的最后一个元素的值就是本题的答案，最低开销。题目详情 On a staircase, the i-th step has some non-negative cost cost[i] assigned ...

fyber 2019-08-16 11:01 评论0 收藏0