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

資訊專欄INFORMATION COLUMN

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

chemzqm / 1606人閱讀

摘要：小鹿題目假設(shè)你正在爬樓梯。需要階你才能到達樓頂。你有多少種不同的方法可以爬到樓頂呢注意給定是一個正整數(shù)。算法思路二種解決思路，第一利用遞歸第二利用動態(tài)規(guī)劃。就是因為有了重復元素的計算，導致了時間復雜度成指數(shù)的增長。

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.

假設(shè)你正在爬樓梯。需要 n 階你才能到達樓頂。

每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？

注意:給定 n 是一個正整數(shù)。

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 ▉ 算法思路 
二種解決思路，第一利用遞歸；第二利用動態(tài)規(guī)劃。
1）遞歸的實現(xiàn)方式：


首先，我們要知道遞歸使用應(yīng)該滿足的三個條件，之前在前邊的題型中講到過，后邊我會整理成系列文章供大家方便學習。然后按照我們之前講過的方式去寫出遞歸公式，然后轉(zhuǎn)化為遞歸的代碼。我們會發(fā)現(xiàn)遞歸的時間復雜度為 O（2^n），我們是否還記得遞歸的缺點有一條就是警惕遞歸重復元素計算。就是因為有了重復元素的計算，導致了時間復雜度成指數(shù)的增長。


為了能夠降低時間復雜度，我們可以用散列表來記錄重復元素記錄過的值，但是需要申請額外的空間進行存儲，導致空間復雜度為O(n)，時間復雜度降為O(n)，也正是利用了空間換時間的思想。


2）動態(tài)規(guī)劃的實現(xiàn)方式：


我們可以仔細發(fā)現(xiàn)上方的遞歸的方式還是可以優(yōu)化的，我們換種方式去思考，從底向上去思考，其實我們計算一個值之存儲之前的兩個值就可以了（比如：計算 f(6) ,需要知道 f(5) 和 f(4) 的值就可以了），我們可以不用存儲之前的值，此時可以將空間復雜度降為 O(1)。
▉ 代碼實現(xiàn)（遞歸） 
優(yōu)化后的遞歸實現(xiàn)。
//遞歸實現(xiàn)
//時間復雜度為 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;
    }
};
▉ 代碼實現(xiàn)（動態(tài)規(guī)劃） 
//動態(tài)規(guī)劃
//時間復雜度為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...

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

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

相關(guān)文章

  • leetcode70 climbing stairs 爬樓梯游戲

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

    姘存按 評論0 收藏0

  • [Leetcode] Climbing Stairs 爬樓梯

    摘要：遞歸法復雜度時間空間思路這題幾乎就是求解斐波那契數(shù)列。最簡單的方法就是遞歸。但重復計算時間復雜度高。代碼遞推法復雜度時間空間思路實際上我們求的時候只需要和的值，所以可以減少一些空間啊。 Climbing Stairs You are climbing a stair case. It takes n steps to reach to the top. Each time you c...

    tinyq 評論0 收藏0

  • [leetcode] Climbing Stairs

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

    int64 評論0 收藏0

  • 【Leetcode】70. 爬樓梯

    摘要：題目假設(shè)你正在爬樓梯。需要階你才能到達樓頂。你有多少種不同的方法可以爬到樓頂呢注意給定是一個正整數(shù)。示例輸入輸出解釋有兩種方法可以爬到樓頂。階階階階階階階題解這個題目只要模擬一下基本就能想到是，狀態(tài)方程寫出來就是斐波那契數(shù)列。 題目 假設(shè)你正在爬樓梯。需要 n 階你才能到達樓頂。 每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？ 注意：給定 n 是一個正整數(shù)。 示...

    raoyi 評論0 收藏0

發(fā)表評論

0條評論

chemzqm

男|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<