題目:
假設(shè)你正在爬樓梯案训。需要 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ī)劃, 一言以蔽之就是, 記住你已經(jīng)做過的計算, 在已經(jīng)計算過的基礎(chǔ)上疊加, 避免重復(fù)的計算.
首先, 不妨將階梯數(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] ......
當(dāng)只有一個階梯走跨兩步時, 就可能出現(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] ......
而當(dāng)兩個階梯走跨兩步時, 可能出現(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]
......
注意到這里兩次跨兩步的情況都是在一次跨兩步的基礎(chǔ)下得的出來的, 具體就是在一次跨兩步的那個兩步之后選擇跨兩步的位置, 這樣避免出現(xiàn)重復(fù)的跨步情況, 又能完整遍歷出結(jié)果, 基于這個方案, 我寫出了第一種算法
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種情況
但是很不幸這種方式超時了, 因為里面還是包含了太多的重復(fù)計算
以數(shù)字8為例:
當(dāng)我們傳入一個8, 他將遞歸計算值為6, 5, 4, 3, 2, 1, 0的結(jié)果
而計算6, 則將遞歸計算4, 3, 2, 1, 0的結(jié)果
計算5將計算3, 2, 1, 0的結(jié)果
...
可以看到, 0的結(jié)果, 1的結(jié)果, 2的結(jié)果將被重復(fù)計算多次, 而這些計算是不需要的
于是我重新觀察這種方案, 當(dāng)n = 0時, 可以直接得出1, 當(dāng)n = 1時可以直接得出1, 當(dāng)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
}
}
提交通過
