題目:
假設你正在爬樓梯。需要 n 階你才能到達樓頂。
每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？
注意：給定 n 是一個正整數(shù)。
示例 1：
輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂
- 1 階 + 1 階
- 2 階
示例 2：
輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂。 - 1 階 + 1 階 + 1 階
- 1 階 + 2 階
- 2 階 + 1 階
看到這題, 腦子里想到的就是動態(tài)規(guī)劃, 什么是動態(tài)規(guī)劃, 一言以蔽之就是, 記住你已經做過的計算, 在已經計算過的基礎上疊加, 避免重復的計算.
首先, 不妨將階梯數(shù)想象成一個全是1組成的數(shù)組, 比如8級階梯, 就是:
[1, 1, 1, 1, 1, 1, 1, 1]
那么不同的爬樓梯方案就類似于:
[2, 1, 1, 1, 1, 1, 1], [1, 2, 1, 1, 1, 1, 1], [2, 2, 1, 1, 1, 1] ......
當只有一個階梯走跨兩步時, 就可能出現(xiàn)7中情況, 即:
[2, 1, 1, 1, 1, 1, 1], [1, 2, 1, 1, 1, 1, 1], [1, 1, 2, 1, 1, 1, 1], [1, 1, 1, 2, 1, 1, 1] ......
而當兩個階梯走跨兩步時, 可能出現(xiàn)如下情況:
[2, 2, 1, 1, 1, 1], [2, 1, 2, 1, 1, 1], [2, 1, 1, 2, 1, 1], [2, 1, 1, 1, 2, 1], [2, 1, 1 ,1, 1, 2],
[1, 2, 2, 1, 1, 1], [1, 2, 1, 2, 1, 1], [1, 2, 1, 1, 2, 1], [1, 2, 1, 1, 1, 2],
[1, 1, 2, 2, 1, 1], [1, 1, 2, 1, 2, 1], [1, 1, 2, 1, 1, 2]
......
注意到這里兩次跨兩步的情況都是在一次跨兩步的基礎下得的出來的, 具體就是在一次跨兩步的那個兩步之后選擇跨兩步的位置, 這樣避免出現(xiàn)重復的跨步情況, 又能完整遍歷出結果, 基于這個方案, 我寫出了第一種算法
func climbStairs(_ n: Int) -> Int {
if n > 0 {
var count = 1
for i in 1..<n {
count += self.climbStairs(n - i - 1)
}
return count
} else {
return 1
}
}
每個臺階總數(shù)全為1, 是一種情況, 然后在這個全為一的數(shù)組中湊出一個2,
得到多種情況, 在每種情況下, 將湊出的那個2去掉, 使2之后剩下的1成為一個新的值, 向下遞歸, 直到n = 0, 這個時候我們知道, 只有1種情況
但是很不幸這種方式超時了, 因為里面還是包含了太多的重復計算
以數(shù)字8為例:
當我們傳入一個8, 他將遞歸計算值為6, 5, 4, 3, 2, 1, 0的結果
而計算6, 則將遞歸計算4, 3, 2, 1, 0的結果
計算5將計算3, 2, 1, 0的結果
...
可以看到, 0的結果, 1的結果, 2的結果將被重復計算多次, 而這些計算是不需要的
于是我重新觀察這種方案, 當n = 0時, 可以直接得出1, 當n = 1時可以直接得出1, 當n = 2時, 可以視為 1 + (n = 0), 以此類推:
n = 0: 1
n = 1: 1
n = 2: 1 + (n = 0)
n = 3: 1 + (n = 1) + (n = 0)
n = 4: 1 + (n = 2) + (n = 1) + (n = 0)
n = 5: 1 + (n = 3) + (n = 2) + (n = 1) + (n = 0)
...
可以觀察到:
n = 4: (n = 3) + (n = 2)
n = 5: (n = 4) + (n = 3)
于是可以通過累加法, 從n = 2開始
記下n = 0 和 n = 1
n = 2 就等于 (n = 0) + (n = 1)
記下n = 1 和 n = 2
n = 3 就等于 (n = 2) + (n = 1)
記下n = 2 和 n = 3
n = 4 就等于 (n = 3) + (n = 2)
...
最終得出答案
func climbStairs(_ n: Int) -> Int {
if n > 1 {
var lastTwo = 1
var addCount = 1
for index in 2...n {
let tLast = lastTwo
lastTwo = addCount
addCount += tLast
}
return addCount
} else {
return 1
}
}
提交通過
