[Leetcode] Climbing Stairs 爬樓梯

tinyq 發布于2019-08-14 12:26 / 1677人閱讀

摘要：遞歸法復雜度時間空間思路這題幾乎就是求解斐波那契數列。最簡單的方法就是遞歸。但重復計算時間復雜度高。代碼遞推法復雜度時間空間思路實際上我們求的時候只需要和的值，所以可以減少一些空間啊。

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)

云服務器 GPU云服務器爬樓梯 Climbing Stairs LeetCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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