一魚多吃 用費式數列的DP模型來解 Climbing Stairs_Leetcode #70
這題乍看之下是新題目，但仔細一想，其實只是前面介紹過的費式數列的小變形而已，解題思想基本不變。
題目可以在這裡看到
題目說每次可以爬一階樓梯或兩階樓梯，問爬到n階的方法數是多少。
對應的詳解影片，搭配服用，效果更佳。
範例輸入輸出如下:
Example 1:
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:
Input: n = 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
複習再複習，Dynamic programming的解題框架可分為三大步驟
1. 定義狀態 [我在哪裡]
2. 定義狀態轉移關係式(通則) [我從哪裡來] => [答案從哪裡推導而來]
3. 釐清初始狀態(也可以說是遞迴的終止條件) [第一步怎麼走，怎麼出發的]
這裡我們走過一遍DP解題框架，可分為三大步驟
1. 定義狀態 [我在哪裡]
這題也滿直覺的，就令DP[n]為爬n階樓梯的方法數。
2. 定義狀態轉移關係式(通則) [我從哪裡來] => [答案從哪裡推導而來]
題目說每次可以爬一階樓梯或兩階樓梯，也就是說
假如當下這層是第n階樓梯，那麼我們有兩種方式可以到達這裡:
一種是先到n-1階，接著再爬一階樓梯，那麼我們就到了第n階。
另一種是先到n-2階，接著再爬兩階樓梯，那麼我們就到了第n階。
用遞迴關係式表示就是
DP[n] = DP[n-1]+ DP[n-2]
其中DP[n-1]這個項代表含先到n-1階再爬一階的意思， 而
DP[n-2]這個項代表含先到n-2階再爬兩階的意思。
如下圖所示
3. 釐清初始狀態(終止條件) [第一步怎麼走，怎麼出發的]
比較敏銳的同學，可以發現，這條遞迴式和大家熟知的費式數列相同。
對的，就是f(n) = f(n-1) + f(n-2)的形式。
唯一的小差別是初始條件不同而已。
爬0階樓梯有幾種方式?只有一種，就是什麼都沒做，沒有爬任何一階階梯。
DP[0] = 1
爬1階樓梯有幾種方式?只有一種，就是從0階往上爬一階就到第1階樓梯。
DP[1] = 1
更高層的2階, 3階…等還需要初始化嗎? 不用了，因為我們已經可以從遞回式DP[n] = DP[n-1] + DP[n-2] 計算出來。
到這裡，已經填滿解題框架的所有內容，接著我們把它轉成程式碼，
這裡以Python作為示範
Top - down DP
class Solution:
def climbStairs(self, n: int) -> int:
# DP table
# key: floor
# value: method count to climb
## Base case
table = {
0: 1,
1: 1
}
def dp( n: int) -> int:
# look-up table
if n in table:
return table[n]
## General case
table[n] = dp(n-1) + dp(n-2)
return table[n]
# ----------------------------------
return dp(n)
Bottom-up DP
class Solution:
def climbStairs(self, n: int) -> int:
# DP table
# key: floor
# value: method count to climb
table = [1 for _ in range(n+1)]
## General case
for i in range(2, n+1):
table[i] = table[i-1] + table[i-2]
return table[n]
時間複雜度:
皆為O(n)，從n階樓梯降階到1階
空間複雜度:
皆為O(n)，DP table和遞迴呼叫深度皆為O(n)
學完這題的同學，記得去複習 費式數列 這題喔，其實兩者背後的DP框架和觀念都是相通的喔!
Reference:
