合縱連橫: 從 數列DP 理解 遞迴數列的本質
這篇文章，會帶著大家複習以前學過的數列DP框架，
並且以費式數列、爬樓梯、骨牌拚接的應用與遞迴數列概念為核心，
貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個演算法框架。
數列DP與遞迴數列常見的形式
如果是遞迴數列，常常看到以函數型式表達
f(n) = f(n-1) ~ f(n-k) 之間的運算組合而成
對應的DP通則就是
DP[n] = DP[n-1] ~ DP[n-k] 之間的運算組合而成
例如，經典的費式數列就是
f(n) = f(n-1) + f(n-2)
f(0) = 0
f(1) = 1
第n項 = 前兩項相加
對應的DP通則就是
DP[n] = DP[n-1] + DP[n-2]
DP初始條件則是
DP[0] = 0
DP[1] = 1
有些比較進階的題目則不會直接給出通則，
需要我們根據題目給的定義和範例推導出來。
費式數列 Fibonacci Number - LeetCode
這題算是很基本的入門題。
題目也很友善的給出通則和初始條件
F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.
依樣畫葫蘆，透過遞迴function + DP查表實現即可。
這題剛好以前有錄過教學影片，提供給讀者參考。
現在通則和初始條件都有了，就可以來寫數列DP的程式碼
class Solution:
def fib(self, n: int) -> int:
dp = {0: 0, 1: 1}
def getFib( i ):
if i in dp:
return dp[i]
dp[i] = getFib(i-1) + getFib(i-2)
return dp[i]
return getFib(n)
爬樓梯 Climbing Stairs - LeetCode
這題題目說從平面出發，每次可以跨一階樓梯或跨兩階樓梯，
請問到n階樓梯有幾種方法?
雖然題目沒有直接給出通則，但是從題目規則和範例可以知道
爬到第n階樓梯 有兩種可能的途徑
第一種是先想辦法到n-1階，再跨一階樓梯，到達第n階。
第二種是先想辦法到n-2階，再跨兩階樓梯，到達第n階。
因此，我們可以定義DP[n] = 到達第n階樓梯的方法數
那麼通則可以寫成這樣的型式
DP[n]
= 第一種途徑 + 第二種途徑
= DP[n-1] + DP[n-2]
仔細一看，其實就是剛剛介紹過的費式數列，核心是相同的，只是換個樣貌出現而以。
那初始條件呢?
可以這樣想
爬到第一階樓梯有幾種方法?
只有一種，就是直接跨一階。
因此，DP[1] = 1
爬到第二階樓梯有幾種方法?
只有兩種，就是直接跨一階，再跨一階。或者，一次跨兩階直接到第二階。
因此，DP[2] = 2
這題剛好以前有錄過教學影片，提供給讀者參考。
現在通則和初始條件都有了，就可以來寫數列DP的程式碼
class Solution:
def climbStairs(self, n: int) -> int:
# Initial step
# C(1) = 1 , 0 -> 1
# C(2) = 2 , 0 -> 1 -> 2 or 0 -> 2
dp = {1: 1, 2: 2}
def climb( i ):
# look-up DP table
if i in dp:
return dp[i]
# general rule: C(i) = C(i-1) + C(i-2)
dp[i] = climb( i-1 ) + climb( i-2 )
return dp[i]
# ------------------------------
return climb(n)
再來看更進階一點的骨牌拼接
骨牌拼接 Domino and Tromino Tiling - LeetCode
題目會給我們兩種無限量供應的骨牌Domino 和 Tromino，形狀分別如下
題目的輸入會有一個參數n。
可以任意旋轉方向進行拼接，請問最後拼成 2 x n 長方形區域的方法數有幾種?
例如 n = 3 時，拼成2 x 3 的長方形區域有五種方法。
這種計算方法數的題目，通常和兩類演算法有關
1.遞回。
為什麼? 因為主要是透過生成規律去推導遞迴關係式，進一步算出方法數。
2.DP 動態規劃
為什麼? 因為如果純粹只依賴遞回計算，很可能會浪費很多時間在計算重複的子問題，因此需要透過DP動態規劃，去儲存已經計算過的答案，之後遇到重複的可以直接查表取得答案，提升演算法執行效率，減少時間複雜度。
第一步其實沒有捷徑，就是真的在紙筆上畫幾個最小規模的拼接情況，觀察生成模式。
可以發現，生成模式可以歸類成以下幾種，左邊是分類，右邊是對應的遞回生成關係。
DP狀態定義
第i層是平的 DP[i][FLAT]
第i層的上面凸一塊 DP[i][SPIKE_UP]
第i層的下面凸一塊 DP[i][SPIKE_DOWN]
因此，歸納整理，可以寫成如下
初始條件
第0層就是空的，空的拼接方式只有一種，就是什麼都不放。
DP[0, FLAT] = 0
第1層是平的拼接方式也只有一種，就是垂直方向放一塊Domino。
DP[1, FLAT] = 0
狀態轉移關係式, 通則(把剛剛示意圖的情況寫成遞迴關係式)
dp[i,FLAT]
= dp[i-1,FLAT] + dp[i-2,FLAT] + dp[i-1,SPIKE_UP] + dp[i-1,SPIKE_DOWN]
dp[i,SPIKE_UP]
= dp[i-2,FLAT] + dp[i-1,SPIKE_DOWN]
dp[i,SPIKE_DOWN]
= dp[i-2,FLAT] + dp[i-1,SPIKE_UP]
現在通則和初始條件都有了，就可以來寫數列DP的程式碼
class Solution:
def numTilings(self, n: int) -> int:
# DP State definition
FLAT, SPIKE_UP, SPIKE_DOWN = 0, 1, 2
# DP table
dp = defaultdict(int)
# Initialization
dp[0,FLAT] = 1
dp[1,FLAT] = 1
# General cases
for i in range(2, n+1):
dp[i,FLAT] = dp[i-1,FLAT] + dp[i-2,FLAT] + dp[i-1,SPIKE_UP] + dp[i-1,SPIKE_DOWN]
dp[i,SPIKE_UP] = dp[i-2,FLAT] + dp[i-1,SPIKE_DOWN]
dp[i,SPIKE_DOWN] = dp[i-2,FLAT] + dp[i-1,SPIKE_UP]
return dp[n,FLAT] % (10**9 + 7)
結語
好，今天一口氣介紹了最精華的部分，
通用的數列DP框架，還有相關的費式數列、爬樓梯、骨牌拼接應用題
與遞迴數列演算法建造，
希望能幫助讀者、觀眾徹底理解它的原理，
並且能夠舉一反三，洞察其背後的本質和了解相關的應用領域！
感謝收看囉! 我們下篇文章再見~
