成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[Leetcode] Climbing Stairs 爬樓梯

tinyq / 1698人閱讀

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

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?
遞歸法 復(fù)雜度

時(shí)間 O(1.618^N) 空間 O(N)

思路

這題幾乎就是求解斐波那契數(shù)列。最簡(jiǎn)單的方法就是遞歸。但重復(fù)計(jì)算時(shí)間復(fù)雜度高。

代碼 
public class Solution {
    public int climbStairs(int n) {
        if(n==1 || n==0) return 1;
        else return climbStairs(n-1) + climbStairs(n-2);
    }
}
動(dòng)態(tài)規(guī)劃 復(fù)雜度

時(shí)間 O(N) 空間 O(N)

思路

將之前計(jì)算過的結(jié)果存下來，節(jié)省了一些時(shí)間。

代碼 
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 復(fù)雜度

時(shí)間 O(N) 空間 O(1)

思路

實(shí)際上我們求n的時(shí)候只需要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];
    }
}
矩陣法 復(fù)雜度

時(shí)間 O(logN) 空間 O(1)

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64473.html

相關(guān)文章

  • leetcode70 climbing stairs 爬樓梯游戲

    摘要：題目要求假設(shè)有級(jí)臺(tái)階為正整數(shù)，每次可以爬一級(jí)臺(tái)階或兩級(jí)臺(tái)階。問有多少種方法爬完級(jí)臺(tái)階遞歸方法最后一步可以是一級(jí)臺(tái)階，或者是兩級(jí)臺(tái)階，一共兩種情況。 題目要求：假設(shè)有n級(jí)臺(tái)階（n為正整數(shù)），每次可以爬一級(jí)臺(tái)階或兩級(jí)臺(tái)階。問有多少種方法爬完n級(jí)臺(tái)階？ 遞歸方法最后一步可以是一級(jí)臺(tái)階，或者是兩級(jí)臺(tái)階，一共兩種情況?？赏ㄟ^遞歸獲得n-1級(jí)臺(tái)階和n-2級(jí)臺(tái)階的和獲得n級(jí)臺(tái)階的結(jié)果臺(tái)階數(shù)量過高的話...

    姘存按 評(píng)論0 收藏0

  • LeetCode 之 JavaScript 解答第70題 —— 爬樓梯（Climbing Stair

    摘要：小鹿題目假設(shè)你正在爬樓梯。需要階你才能到達(dá)樓頂。你有多少種不同的方法可以爬到樓頂呢注意給定是一個(gè)正整數(shù)。算法思路二種解決思路，第一利用遞歸第二利用動(dòng)態(tài)規(guī)劃。就是因?yàn)橛辛酥貜?fù)元素的計(jì)算，導(dǎo)致了時(shí)間復(fù)雜度成指數(shù)的增長(zhǎng)。 Time：2019/4/12Title:Clibing SrairsDifficulty: EasyAuthor:小鹿 題目：Climbing Stairs You a...

    chemzqm 評(píng)論0 收藏0

  • [leetcode] Climbing Stairs

    摘要：實(shí)質(zhì)就是把之前出現(xiàn)過的中間結(jié)果記錄，下次再出現(xiàn)相同情況的時(shí)候，通過可以只用的時(shí)間復(fù)雜度得到。表示到達(dá)第層樓梯的不同走法。那么題目中每次可以選擇走一步，或者兩步，。從迭代公式可以知道，有兩個(gè)，和。 70. Climbing Stairs You are climbing a staircase. It takes n steps to reach to the top.Each tim...

    int64 評(píng)論0 收藏0

  • 前端 | 每天一個(gè) LeetCode

    摘要：在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...

    張漢慶 評(píng)論0 收藏0

  • leetcode 746 Min Cost Climbing Stairs

    摘要：同時(shí)你可以選擇從第階開始或者第一階開始。我們的目標(biāo)是找出你爬到最頂層所付出的最小的開銷。最低開銷是，從第階開始，只花費(fèi)就可以到頂層。想法動(dòng)態(tài)規(guī)劃問題。的長(zhǎng)度應(yīng)該為數(shù)組長(zhǎng)度加一，其中數(shù)組的最后一個(gè)元素的值就是本題的答案，最低開銷。 題目詳情 On a staircase, the i-th step has some non-negative cost cost[i] assigned ...

    fyber 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<