題目描述
假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂歇攻。
每次你可以爬 1 或 2 個臺階驮樊。你有多少種不同的方法可以爬到樓頂呢？
注意：給定 n 是一個正整數(shù)柑晒。
示例 1：
輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂欧瘪。
1. 1 階 + 1 階
2. 2 階
示例 2：
輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂。
1. 1 階 + 1 階 + 1 階
2. 1 階 + 2 階
3. 2 階 + 1 階
思路
每次可以爬 1 或 2 個臺階敦迄。當(dāng)我們爬 4 個臺階時恋追，就是爬 3 個臺階的方法數(shù)，加上爬 2 個臺階的方法數(shù)罚屋，等于 F(3) + F(2) = 3 + 2 = 5苦囱。所以當(dāng)我們爬 N 個臺階，就有 F(N - 1) + F(N - 2) 種方法脾猛。
解決方案
方案一：暴力破解
我們可以用遞歸的方法得到所有小于N的方法數(shù)撕彤，并把它們相加得出結(jié)果。遞歸結(jié)束的標(biāo)志為 N=1 或 N =2猛拴。
var climbStairs = function(n) {
if (n == 1) return 1
if (n == 2) return 2
return climbStairs(n - 1) + climbStairs(n - 2)
};
時間復(fù)雜度 O()羹铅。這種暴力解題的方法會超出時間限制，顯然不是我們想要的愉昆。
方案二：優(yōu)化暴力破解
從上一種方法我們可以發(fā)現(xiàn)职员，每一步的結(jié)果都做了上一步的重復(fù)計算。比如F(6) + F(5) 后會計算 F(5) + F(4)跛溉，F(xiàn)(5) 我們已經(jīng)計算過了焊切，就不要重復(fù)計算了。所以我們可以用一個數(shù)組來儲存計算結(jié)果芳室，方便重復(fù)利用专肪。
var climbStairs = function(n) {
let arr = []
function climb(n) {
if (n == 1) return 1
if (n == 2) return 2
if (arr[n] > 0) return arr[n]
arr[n] = climb(n - 1) + climb(n - 2)
return arr[n]
}
return climb(n)
};
時間復(fù)雜度 O(n)，優(yōu)化之后提高了速度堪侯，已經(jīng)不會超出時間限制了嚎尤。
方案三：問題分解
和遞歸的思路一樣，把一個大問題分解成多個小問題伍宦，只是這次我們使用循環(huán)的方式芽死，減少內(nèi)存的開銷乏梁。
var climbStairs = function(n) {
if (n == 1) return 1
if (n == 2) return 2
let arr = []
arr[1] = 1
arr[2] = 2
for (let i = 3; i<= n; i++) {
arr[i] = arr[i - 1] + arr[i - 2]
}
return arr[n]
};
時間復(fù)雜度 O(n)，優(yōu)化了內(nèi)存的消耗收奔，速度沒有提升掌呜。
方案四：斐波那契數(shù)
從上一個方案我們可以看出這是一個斐波那契數(shù)列。
var climbStairs = function(n) {
if (n == 1) return 1
if (n == 2) return 2
let first = 1
let second = 2
for (let i = 3; i<= n; i++) {
let third = first + second
first = second
second = third
}
return second
};
時間復(fù)雜度 O(n)
