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

chemzqm 發布于2019-08-23 16:55 / 1595人閱讀

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

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必問面試題

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

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