一魚多吃 用費式數列的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. 定義DP狀態 [我在哪裡]

2. 推導DP狀態轉移關係式(通則) [我從哪裡來] => [答案從哪裡推導而來]

3. 釐清DP初始狀態(也可以說是遞迴的終止條件) [第一步怎麼走，怎麼出發的]

這裡我們走過一遍DP解題框架，可分為三大步驟

1. 定義DP狀態 
[我在哪裡]

這題也滿直覺的，就令DP[n]為爬n階樓梯的方法數。

2. 定義DP狀態轉移關係式(通則)
[我從哪裡來] => [答案從哪裡推導而來]

題目說每次可以爬一階樓梯或兩階樓梯，也就是說

假如當下這層是第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(1)時間內計算完成。

空間複雜度:O(n)

DP table和遞迴呼叫深度皆為O(n)

學完這題的同學，記得去複習 DP動態規劃 深入淺出 以Fibonacci Number 費式數列 為例 這題喔，其實兩者背後的DP框架和觀念都是相通的喔!

下一篇: 活用DP: 泰伯納西數列的第n項 Leetcode #1137_精選75題

Reference:

[1] DP動態規劃 深入淺出 以Fibonacci Number 費式數列 為例｜方格子 vocus