從零開始進入動態規劃的世界（二）- 尋找狀態轉移公式的方法

11 min readAug 24, 2024

承續上一篇，這篇的題目仍然不會太困難，但我會講得很細，對於已經大致理解過這幾題的人可能會覺得有點冗長，但如系列開頭所說，我正是希望透過這些反覆追根究的思考過程，幫助大家把關於動態規劃的基底一口氣打好，讓我們反覆用相同的流程去處理問題，這是很有價值的事，因為這些簡單的問題真正的重點不在於解出來，而在於培養熟悉的流程感，練熟以後，碰到更困難的問題，就不會茫無頭緒了。

另外很多地方我也期望讀者可以停下來，先自己想一下答案，這樣會對你最有幫助，但如果真的沒時間，就直接看完也沒關係。

好了，那我們開始吧！

爬樓梯

很經典的問題，簡單說就是有一個長度固定的階梯，然後有個奇怪的小屁孩，他堅持只用兩種方式爬樓梯，一次走一階，或一次跳兩階。然後有個更奇怪的人，想問你這樣的話，小屁孩有多少種不重複的走法可以走到最上面？

舉個例子，假設我樓梯有四階，那可能的不同走法有

1 + 1 + 1 + 1
1 + 1 + 2
1 + 2 + 1
2 + 1 + 1
2 + 2

答案就是 5。

若想看原題目的話，連結在此：Climbing Stairs

現在，請你用動態規劃解決這個問題，先想想看！如果感覺沒有頭緒，就讓我們遵照上一篇的流程來吧。

如果我們能先做出一張表，怎樣的表可以幫助你得到答案
這張表上，每一個位置的 key 跟 value 會是什麼？這就是你的狀態定義
表上某一個位置的值，跟另外一些位置之間的轉換是什麼？這就是你的狀態轉移

再停一下，先想想，最少前兩個問題應該可以想出來，通常題幹的描述，幾乎就是狀態函數。

好，我們來解答了。既然題目問的是：有多少種方式爬到最上層

記得動態規劃不會只給你一個答案，他會順便把比較小的問題的答案都給你，所以雖然題目問的是最上層，但我們想的是，有沒有可能我乾脆把每一層的可能方式都找到。

所以，我要的表就是

那狀態函數就是

f(層數）= 有幾種可能走法

而我們最後要的答案就是 f(最頂層的層數），已經可以想像程式大概會長成以下這樣了

def climbStairs(int n):
  dp = [0] * n # 開一個 Array 紀錄，index 代表層數，值則代表攀爬的可能方式
  dp[1] = 1 # 初始化，若把地板當作第 0 層，那第 1 層，一定只有一種走法，就是走一格

  for i in range(1, n+1):
      # 這邊你會經由狀態轉移，逐步把 index 1 ~ n 的答案都找到
   
  return dp[n] # 回應頂層的值即可

那接著就是，狀態怎麼轉移了，也是這題真正的難點。這邊介紹一下想狀態轉移的常見方式

隨便抽一個位置，然後想著，如果我已經知道了所有更前面的位置的答案，能不能協助我算出當前位置的答案？

例如我想問 f(5)，但我不知道答案，不過，假設我已經知道了 f(4), f(3), f(2), f(1) ，這些東西能不能幫我算出 f(5)？

一樣，先停一下，想一想

如果還沒想法，提示

要走到 f(5)，也就是說，要走到第五層，他的前一步有那些可能？

由於小屁孩只可能走 1 階或跳 2 階，所以前一步，一定只可能是在第三層或第四層。所以他一定跟 f(3) 或 f(4) 有點關聯。

要公佈答案囉

怎麼關聯呢？讓大家看看我的思路

假設我已知有 x 種不同方法可以走到第三層，有 y 種不同方法可以走到第 4 層
不管我前面怎麼走的，假設最後一步是從第 3 層一次跳兩階，跟最後一步是從第 4 層往上走一階，這兩大種類型的做法，保證是不同的，因為他們的最後一步行為不同，不可能被重複算到。
所以我們應該可以直接先把他們加起來，也就是說 f(5) 最少有 x + y 種不同走法

但，還有其他可能性嗎？

那我從第三層，走兩次一階，走到第五層，這種可能性不用考慮嗎？想一下，如果我走兩次一階，那我一定有經過第 4 層對吧，那其實這種可能性，已經被包含在”第 4 層往上走 1 階” 的時候算過了，所以不用重複。

依此類推，若是從第二層或第一層走上來的，不管走法怎樣，一定也都會先經過第三、或第四層，才能到第五層，那這些可能走法也就已經都在 f(3) 與 f(4) 裡面被算到了。

最後，我們會發現，f(5) 就是 f(4) + f(3)，而每個位置跟前面的關聯性，其實都應該要是一樣的，所以，我們得到更通用狀態轉移方程式就是。

f(x) = f(x-1) + f(x-2)

恩，然後你發現，他基本就是個費氏數列，是吧。因此我們的程式碼可以填上最後的洞了。

def climbStairs(int n):
  dp = [0] * n # 開一個 Array 紀錄，index 代表層數，值則代表攀爬的可能方式
  dp[1] = 1 # 初始化，第一層，一定只有一種走法

  for i in range(2, n+1):
      dp[i] = dp[i-1] + dp[i-2]
   
  return dp[n] # 回應頂層的值即可

完成了！… 嗎？

錯了！想想看，哪邊錯了？

答案是初始化的地方錯了！稍微讓我們囉唆一下。因為初始化其實也是動態規劃問題的一大難點，對於比較複雜的題目，怎樣好好的初始化有時候是會讓人煩惱一陣子的，我們很有必要趁著簡單題目來好好聊聊，才不會到後面突然讓人嚇到，怎麼這麼複雜？

之前費式數列，我們初始化 fab[0] = fab[1] = 1，因為根據費式數列的定義就是這樣。但現在的爬樓梯稍稍沒那麼直覺。所以初始化該怎麼思考呢？

通常想法是這樣，由於接近最小的幾個答案，通常心算一下就知道了，新手階段，我們可以先手算出幾個。

例如第一層是一種走法（1 step），第二層的話，會是兩種 (1 step + 1 step 或 2 steps)。那我就可以先初始化下來

dp[1] = 1
dp[2] = 2

那，要初始化到第幾個才夠用呢？第三、第四層要不要順便心算一下？通常判斷夠不夠的標準很簡單，回去看狀態轉移！

狀態轉移公式是 dp[i] = dp[i-1] + dp[i-2]

所以，你最少要有 2 個東西才能啟動對吧？如果你想從 dp[2] 開始算，你需要先有 dp[1] 跟 dp[0]。而如果你想從 dp[3] 開始，也會需要先有 dp[2] 或 dp[1] 預先被設定好。這些預先設定就是初始化。

但以這題來說 dp[0] 到底是什麼意思？第零層有幾種走法？完全不動，到底算 1 種方式還是算 0 種方式？根本沒定義對吧！這就是個有點弔詭的地方，並沒有那麼直覺，這邊，我提供兩種思路。

思路 1:

可以想想第二層，如果我們把從第零層（地板），靠一個 2 steps 跳到第二層的做法，視為一種可能的走法，而從第一層，靠一個 1 step 走到第二層，也算一種走法。由於轉移方式是 dp[2] = dp[1] + dp[0]。那第零層跟第一層的意義應該視為相同，都視為本身有 1 種走法存在，這樣第二層，才會是 2 種走法，跟我們想要的吻合。這樣寫出來的程式碼會是：

def climbStairs(self, n: int) -> int:
  dp = [0] * (n+1)
  dp[0] = 1 # 把第零層的值初始化為 1，這是題目中沒有講，由我們自己賦予他意義
  dp[1] = 1

  for i in range(2, n+1):
    dp[i] = dp[i-1] + dp[i-2]

  return dp[n]

思路 2:

如果你覺得這種硬塞給第零層意義的方式實在很難接受，那也無妨，我們可以乾脆就拋棄他，反正題目中 n 的範圍就已經限定在 1 ~ 45，不可能出現 0。另外，我又只需要”兩個連續的”初始值，就可以啟動計算，那我乾脆直接初始化第一層跟第二層，之後從第三層開始算下去。這樣寫出來的程式碼會是：

def climbStairs(self, n: int) -> int:
  dp = [0] * (n+1)
  dp[1] = 1
  dp[2] = 2 # 心算出來的已知結果

  for i in range(3, n+1): # 從第 3 層開始跑動態規劃計算
    dp[i] = dp[i-1] + dp[i-2]

  return dp[n]

但！小心細節，再次提醒，動態規劃的每個細節都很重要。讀者可以自我挑戰一下，想想上面這個寫法漏了什麼？

由於最初的題目告訴你 n 的可能 input 範圍是 1~45。所以你要額外處理一下 n == 1 的狀況，否則上面的程式碼會爆掉，然後你就會得到一個 Wrong Answer 的紅色大字。因此，最終要寫成。

def climbStairs(self, n: int) -> int:
  if n == 1: # 補上邊界條件的例外判斷
    return 1

  dp = [0] * (n+1)
  dp[1] = 1
  dp[2] = 2

  for i in range(3, n+1):
    dp[i] = dp[i-1] + dp[i-2]

  return dp[n]

這樣做就是程式碼稍微囉唆一點，而且要多心算一個值，但如果你覺得這樣的想法比較舒服，就這樣寫也很好，思路是清晰的，答案也是正確的。

如果你以前時常看別人寫的動態規劃題解，可能也會看到好幾個相似但又有微妙不同的寫法，常常就是發生在這個初始值的設定上。未來我們會看到更多時候，這個初始值沒這麼好想。

這確實是動態規劃的另一個難點之一，有時候我們還會為了讓程式更簡潔，故意錯位一下，例如讓 index 0 代表第一層，index 1 代表第二層之類的。甚至也可能去定義假想的 index -1 的值，來讓 index 0 的值正常化。但，先不要被繞暈，也不用怕，這些都只是技巧，動態規劃的本質並沒有改變，如果你對這些花招感到不舒服，一定都有老老實實做的方式，頂多只是程式碼比較囉唆，要注意的細節比較多。我們後續會繼續看到很多這樣的例子。

額外提個我自己學習的經驗，我覺得新手階段去追求”很漂亮”的寫法是沒有意義的，甚至有點危險，因為那裡面可能參雜了太多技巧轉折，反而讓你忽略核心重點，若有時你覺得自己看懂了一題解答，但稍微變一下就又卡住，這有可能是原因之一。

所以，至此，讓我們再不厭其煩的，重新整理一下，動態規劃最重要的核心思維邏輯。首先，先找出兩件事：

狀態定義
狀態轉移的方式

再來，如何尋找狀態定義？

在簡單的題目上，通常就是題幹跟你說，當 xx 的時候，給我 oo，那這個 xx 一般就是 key，而 oo 就是 value。（例如問當階梯長度為 n 時，有幾種走法，那階梯長度就是 key，走法數量就是 value）
先不要想著只解決題目問的問題，想成我要一口氣解決所有類似問題，例如問你第 n 層有幾種走法，你會想著那我乾脆算出每一層有幾種走法。

然後是，如何尋找狀態轉移，這邊我們想的是