資訊專欄INFORMATION COLUMN
摘要：小鹿題目假設(shè)你正在爬樓梯。需要階你才能到達(dá)樓頂。你有多少種不同的方法可以爬到樓頂呢注意給定是一個(gè)正整數(shù)。算法思路二種解決思路，第一利用遞歸第二利用動(dòng)態(tài)規(guī)劃。就是因?yàn)橛辛酥貜?fù)元素的計(jì)算，導(dǎo)致了時(shí)間復(fù)雜度成指數(shù)的增長(zhǎng)。
Time：2019/4/12
Title:Clibing Srairs
Difficulty: Easy
Author:小鹿
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 階你才能到達(dá)樓頂。
每次你可以爬 1 或 2 個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢？
注意:給定 n 是一個(gè)正整數(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 stepslove ▉ 算法思路
二種解決思路，第一利用遞歸；第二利用動(dòng)態(tài)規(guī)劃。▉ 代碼實(shí)現(xiàn)（遞歸）1）遞歸的實(shí)現(xiàn)方式：
首先，我們要知道遞歸使用應(yīng)該滿足的三個(gè)條件，之前在前邊的題型中講到過(guò)，后邊我會(huì)整理成系列文章供大家方便學(xué)習(xí)。然后按照我們之前講過(guò)的方式去寫出遞歸公式，然后轉(zhuǎn)化為遞歸的代碼。我們會(huì)發(fā)現(xiàn)遞歸的時(shí)間復(fù)雜度為 O（2^n），我們是否還記得遞歸的缺點(diǎn)有一條就是警惕遞歸重復(fù)元素計(jì)算。就是因?yàn)橛辛酥貜?fù)元素的計(jì)算，導(dǎo)致了時(shí)間復(fù)雜度成指數(shù)的增長(zhǎng)。
為了能夠降低時(shí)間復(fù)雜度，我們可以用散列表來(lái)記錄重復(fù)元素記錄過(guò)的值，但是需要申請(qǐng)額外的空間進(jìn)行存儲(chǔ)，導(dǎo)致空間復(fù)雜度為O(n)，時(shí)間復(fù)雜度降為O(n)，也正是利用了空間換時(shí)間的思想。
2）動(dòng)態(tài)規(guī)劃的實(shí)現(xiàn)方式：
我們可以仔細(xì)發(fā)現(xiàn)上方的遞歸的方式還是可以優(yōu)化的，我們換種方式去思考，從底向上去思考，其實(shí)我們計(jì)算一個(gè)值之存儲(chǔ)之前的兩個(gè)值就可以了（比如：計(jì)算 f(6) ,需要知道 f(5) 和 f(4) 的值就可以了），我們可以不用存儲(chǔ)之前的值，此時(shí)可以將空間復(fù)雜度降為 O(1)。
優(yōu)化后的遞歸實(shí)現(xiàn)。
//遞歸實(shí)現(xiàn)
//時(shí)間復(fù)雜度為 O(n)，空間復(fù)雜度為 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;
}
};
▉ 代碼實(shí)現(xiàn)（動(dòng)態(tài)規(guī)劃）
//動(dòng)態(tài)規(guī)劃
//時(shí)間復(fù)雜度為O(n) 空間復(fù)雜度為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 倉(cāng)庫(kù)，可以向 me 提交您其他語(yǔ)言的代碼。在倉(cāng)庫(kù)上堅(jiān)持和小伙伴們一起打卡，共同完善我們的開源小倉(cāng)庫(kù)！
Github：https://github.com/luxiangqia...
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/103522.html
摘要：題目要求假設(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)階，一共兩種情況。可通過(guò)遞歸獲得n-1級(jí)臺(tái)階和n-2級(jí)臺(tái)階的和獲得n級(jí)臺(tái)階的結(jié)果臺(tái)階數(shù)量過(guò)高的話...
摘要：遞歸法復(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 c...
摘要：實(shí)質(zhì)就是把之前出現(xiàn)過(guò)的中間結(jié)果記錄，下次再出現(xiàn)相同情況的時(shí)候，通過(guò)可以只用的時(shí)間復(fù)雜度得到。表示到達(dá)第層樓梯的不同走法。那么題目中每次可以選擇走一步，或者兩步，。從迭代公式可以知道，有兩個(gè)，和。 70. Climbing Stairs You are climbing a staircase. It takes n steps to reach to the top.Each tim...
摘要：題目假設(shè)你正在爬樓梯。需要階你才能到達(dá)樓頂。你有多少種不同的方法可以爬到樓頂呢注意給定是一個(gè)正整數(shù)。示例輸入輸出解釋有兩種方法可以爬到樓頂。階階階階階階階題解這個(gè)題目只要模擬一下基本就能想到是，狀態(tài)方程寫出來(lái)就是斐波那契數(shù)列。 題目 假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。 每次你可以爬 1 或 2 個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢？ 注意：給定 n 是一個(gè)正整數(shù)。 示...
閱讀 3242·2023-04-26 02:33
閱讀 3174·2023-04-25 21:33
閱讀 985·2021-09-02 09:56
閱讀 3012·2019-08-30 15:44
閱讀 2522·2019-08-30 13:15
閱讀 1096·2019-08-30 13:04
閱讀 1715·2019-08-29 15:09
閱讀 4071·2019-08-26 18:26
