從零開始進入動態規劃的世界（一）- 基礎中的基礎
其實想寫這個主題很久了，但總是缺乏了一點決心去做這件事，因為寫這系列真的需要不少力氣，而總是會有更想做但需要花的精力更少的事會插隊進來。
如果你在學習資料結構與演算法的路上，總是覺得動態規劃很難，聽到這四個字就害怕，碰到這個標籤的題目就想跳過，也或許是曾經努力奮發起來面對過這個難關，看過了很多的題解，好像每次都免強看懂了什麼，有所進步，但下次碰到一樣的問題，腦袋還是忘的一干二淨，或即便記得，稍微轉個方向問，又好像是全新的一題毫無頭緒，覺得自己就是對這東西沒辦法。那，這個系列就是為你寫的了！
其實如果只是想找動態規劃的教學，隨便 Google 一下應該都多到這輩子看不完，但大家還是覺得很難，為什麼？他確實真的有難的地方，我也不可能拔掉他那塊真的需要你好好花上一段時間跟精力才能弄懂的邏輯部分，但我可以讓他進入障礙變低，階梯變細，透過一小步一小步的往前走，最終掌握起整個動態規劃的思維邏輯，這是我想做的事。
因此，這系列雖然也會放一些經典問題，但重點都不是題解，而是背後的思維方式，怎樣從零開始，慢慢往前進，逐步推敲出解決方案。如果你只想看題目與解答的話，這系列或許不適合，因為我不僅不會簡單直白告訴你答案，反而可能帶你多繞很多地方，但在這繞路的目的，是期望幫助你逐步掌握真正動態規劃的各項核心思維。
事實上，光是”動態規劃”這個乍看意義不明又好像很厲害的名字，本身就有點誤導。它本質上其實也就只是一些很基礎東西的組合運用而已。所以讓我們先放掉這個名字吧，回到源頭從基礎講起吧，這我認為最容易掌握複雜問題的方式。
最終的期望是，你不是只是理解少數幾個單獨問題的解法，而是能廣泛在腦中建立出一種全局想像，幫助你判斷一個實際的問題，是否適合動態規劃？適合的特徵是什麼？目標是要找什麼？該找什麼？找的時候一般都在想什麼？… 等等。
前情提要已經有點長了，先講到這就好，接下來我們就直接開始吧！
首先，先從結果來感受一下，通常用上動態規劃後，我們最終會得到什麼。
一般來說，用完動態規劃，你會得到的是一個查詢表。程式中就是一個 Hash Map或 Array
這間公司有多少人？
舉個例子，假如今天你想問我某間公司的員工有多少人，那，假如我是先有一張 Hash Map，其中 key 是公司名稱而 value 是人數，這張表紀錄了全世界所有公司的人數資訊，這樣你要的答案，只要查表就有了，簡單吧。
當然，因為人數也是個隨時間變動的資訊，所以本來的問題可能不夠好，你應該問某一年，某間公司有多少人。這時你如果需要一張查詢表，就得要兩個維度，年份數字跟公司名字，那表可能就會變成這樣。
而這種查詢表，就是動態規劃用完之後很可能會得到的東西
動態規劃的結果，通常不僅是回答你原本的問題，而是把整張查詢表先全做出來，最後再查表回答你的問題。
現在，我們給這個查詢表 Hash Map 一個特別的名字，稱作”狀態函數”，之所以叫函數，是因為分析問題時，我們往往用數學中的離散函數 f(x) 去表達。以這個問題來說，函數的定義就是：
f(年份, 公司) = 人數
由於資料是離散的，所以這函數在程式上，也可等同於一個 key 是（年份數字、公司名稱），而 value 是人數的 Hash Map。
但，當然不是只要想查表，就能用動態規劃，上面這個例子來說，你這張表要怎麼得到？大概只能老實的去搜集資料做分析吧。所以…
在眼前這個問題上，動態規劃是幫不上忙的！
那怎樣的問題才行？讓我們把他稍稍改一下
奇怪的公司
如果今天我一樣要問公司人數，但我只要一間特定的奇怪公司，這間公司創立在 1970 年，草創時只有 10 個人，而這間公司的老闆有個怪僻，要求每年就是要增加 25% 的人數，並無條件進位至整數，那我想問你在 2024 年的公司總人數有多少。
此時，我們的狀態定義改成
f(年份) = 人數
而且，又額外多了兩個寶貴資訊，可以稱之為初始值與狀態轉移公式
- 初始值：f(1970) = 10
- 狀態轉移公式：f(x) = ceil( f(x-1) * 1.25 )
註：轉移公式就是告訴你，每年 f(x)，會是去年 f(x-1) 的 1.25 倍，然後取 ceil，在 python 中，ceil 代表無條件進位。
現在我們可以光靠這幾件事，把一路到 2024 年的所有年份人數資訊，一個一個算出來了。
f(1970) = 10
f(1971) = ceil( f(1970) * 1.25 ) = ceil( 10 * 1.25 ) = ceil( 12.5 ) = 13
f(1972) = ceil( f(1971) * 1.25 ) = ceil( 13 * 1.25 ) = ceil( 16.25 ) = 17
...若把這個過程都記錄下來，會變成一張表
最後我就是告訴你表上 2024 那個位置的值而已，整套程式碼可以這樣寫
import math
def memberCount(year: int): # year > 1970
hash_map = {1970: 10} # 初始值：1970 年的時候有 10 個人
for y in range(1971, year + 1):
hash_map[y] = math.ceil(hash_map[y-1] * 1.5) # 狀態轉移公式
return hash_map[year]
print(memberCount(2024))程式中你會看到，雖然你只是想問 2024 的答案，我們其實把 1970~2024 的答案全都算出來存在 hash_map 內，最後回你 hash_map[2024] 那筆資料。
這做法已經很不錯，但讓我們再延伸一下，由於你今天已經知道輸入都會是整數，或者更精確的說，你 Hash Map 的 key 都是整數，而且還是連續的，那你大可不用 Hash Map，改用 Array 紀錄更方便，其中 Array 的 index 就是 key。實際案例中，往往用 Array 做查詢表的情境更常見，此時程式碼可以寫成：
import math
def memberCount(year: int): # year > 1970
n = year - 1970 # 想詢問的年度，與 1970 差距 n 年
arr = [0] * (n + 1) # 初始化：開一個足夠長度的陣列
arr[0] = 10 # 設定初始值：用 index 0 代表 1970 年，此時有 10 個人
for i in range(1, n + 1):
arr[i] = math.ceil(arr[i-1] * 1.5) # 狀態轉移公式
return arr[n] # 回答第 1970 + n 年的值，也就是 array index = n 的值
print(memberCount(2024))寫完了！我抽象一下基本結構，其實就是五行程式碼而已
def solution(n: int):
arr = [0] * (n + 1) # 狀態函數的初始化：開一個足夠長度的陣列
arr[0] = ... # 設定初始值
for i in range(1, n + 1):
arr[i] = ... # 用狀態轉移公式，把每個位置的值都算出來
return arr[n] # 用第 n 個位置的值做為答案回傳請好好記得這五行，因為幾乎所有動態規劃的問題，基本結構大概都是這樣。
看到這邊，一些聰明的讀者可能會想，如果我都知道每年增加 25%，那我直接計算 10 * 1.25 ^ (n -1970) 不行嗎？需要搞這麼麻煩嗎？
是的！這想法大致正確，但以這題來說，這樣會忽略每年都要無條件進位至整數的要求，所以答案不對。不過，假如他的狀態轉移公式是每年成長 100%（也就是每年乘以 2），讓你有辦法直接算出目標答案，確實就沒必要這樣傻傻的全部算一遍了。
更廣泛的來說就是，若狀態轉移函示太過簡單，能用其他方式直接獲得答案，那即便我們仍然可以用動態規劃做，但沒有意義，反而是浪費時間。好好思考清楚這個問題，這對於你將來掌握“到底該不該用動態規劃”很重要。
所以，對於什麼時候該用動態規劃，什麼時候不行，我們現在有了一個粗淺的認識了。
- 如果做出查詢表也沒用的問題，不適用
- 如果查詢表中的每個狀態互相沒關聯，無法靠某些狀態去算出其他狀態的值，不適用
- 如果每個狀態有關連，但關聯之間有特殊的性質，讓你可以用其他簡單解法直接得到答案就好，不適用
到這裡應該可以感受到，雖然用完動態規劃的最終結果，會把查詢表做出來，但這並不是他最一開始的目標，更像是一種迫不得已。
因為我們沒有除了把中間每個值都算出來以外的更好做法，所以只好這樣”暴力”解決。
現在，讓我們用這個前提，重新來看看萬年經典例子費氏數列吧！如果你看過這題一百次了，請原諒我… 我相信再看這次是會有價值的。如果是第一次看到，也沒關係，我還是會從頭講起。
費氏數列
費氏數列： 1, 1, 2, 3, 5, 8, 13, 21, 34, … 這數列當中的每個數字，都是前兩個數字相加的結果，例如 5 = 2+3、13 = 5+8、… 依此類推。
若用數學定義，可以描述成 一個 fib(x) 函數 ：
1. fib(0) = fib(1) = 1
2. 對於任意正整數 x ≥ 2，fib(x) = fib(x-1) + fib(x-2)
而題目就是，給你任意一個 k（0 < k < 1e7)，請告訴我 fib(k) 的值。
如果前面還記得，你會發現，他的題幹基本上就已經包含了狀態函數定義、狀態轉移公式、還有初始值，且又沒有簡單的數學公式能直接算出來某個位置的答案。只要套前面的寫法，豈不就是一個”題幹已經把答案講完”的動態規劃題？
PS: 這邊有人可能會冒出疑問：難道真的沒有簡單的數學公式嗎？你怎麼知道一定沒有？還是你沒找到而已？那你問到好問題了！這確實是個大哉問。而往往我們也很難真的像個數學家一樣，去糾結詳細扎實的證明。
一般來說，工程師的辦法就是，如果你左想右想，就是找不到簡單做法，那就放棄吧，試試動態規劃，我們就是如此樸實無華又簡單的生物。另外有些判斷方式就是依靠時間複雜度，如果算一算還在合理範圍，起碼比暴力解要來得好，那可以嘗試看看。文章更後面我們會聊到時間複雜度的計算。
好，讓我們回來，先相信這題沒有更好的做法，老實的用動態規劃吧，你會發現根本就像填空一樣，下面 Q1 ~ Q3 填完就結束了。
def solution(n: int):
arr = [0] * ? # Q1
arr[0] = ? # Q3
for i in range(1, n + 1):
arr[i] = ? # Q2
return arr[n]Q1：狀態函數 f(x) 的定義是什麼
很顯然，狀態函數就是題幹的 fib(x)，因為我們題目就是要問 x 等於多少的時候，fib(x) 是多少。
Q2：狀態轉移方程式是什麼？
狀態轉移方程式，意思就是說，某個已知的狀態，如果要變成另一個狀態，他們之間的數學式長怎樣？那以這題來說，題幹又已經就是答案。狀態轉移方程式就是 f(x) = f(x-1) + f(x-2)。
Q3：初始值是什麼
很顯然就是 f(0) = f(1) = 1 對吧？
def fibonacci(n: int):
fib = [0] * (n + 1) # 初始化：開一個足夠長度的陣列
fib[0] = fib[1] = 1 # 設定初始值
for i in range(2, n + 1):
fib[i] = fib[i-1] + fib[i-2] # 狀態轉移公式
return fib[n] # 回傳第 n 個位置的值就這樣，幾乎就是照抄算上面的核心程式碼對吧。但小細節很重要，注意到我們這邊的 for loop 從 2 開始而不是從 1，因為 index 0 跟 index 1 的值都已經在初始化時就給了。
到這邊，大家應該對查詢表、狀態函數、狀態轉移公式有一點感覺了。現在讓我們換個角度重新看一次發生了什麼事。
前面說，動態規劃之所以要做出一張查詢表，是因為迫不得已，沒有除了把所有狀態都算出來的更好的做法。但我們也可以有另一種更樂觀的解釋方式，這張查詢表，其實是一種協助你加速計算的副產物，畢竟會用上動態規劃，就是因為：
- 這個問題有個特性（狀態轉移公式），告訴我可以靠著小問題的答案們，去協助找出大問題的答案。
- 在沒有更好的辦法時，我們只能老實的一路由小到大把答案全部找出來。
- 在找的過程中，若把結果暫存在查詢表中，才能方便我們用小問題的答案去組合出大問題。
到這邊，如果有人看過我之前寫的遞迴相關系列
一次看懂遞迴 (Recursion) 的思維模式（一）- 遞迴的基礎思維
或者是本來就對遞迴很熟悉，可能會感覺到一絲絲的似曾相似，怎麼這第一句話跟遞迴的描述一模一樣？是的，其實動態規劃如果換個角度來說，他在做的事情就是遞迴，只是加上了一個記錄器，也就是我們一直反覆提的查詢表，來幫助我們加速。
那為什麼前面的程式完全沒看到遞迴的影子？不都是個 for loop 嗎？沒錯，但讓我們換個寫法。
def fibonacci(x): # x >= 0
if x == 0 or x == 1:
return 1
return fibonacci(x-1) + fibonacci(x-2)做完了，你看這狀態轉移公式，豈不就是妥妥的遞迴暗示嗎！但小心！你還必須加上一個記錄器，也就是我們上面一直談的狀態函數、f(x)、hash map。這邊，我們用一個 `fib` array 來做紀錄。
fib = [0] * (n+1) # 初始化，先全部設為 0（注意！要用答案不可能出現的數字來初始化）
def fibonacci(x): # x >= 0
if x == 0 or x == 1: # 已知的初始值，直接回傳
# 也可以順便紀錄上去 fib[x] = 1，但不記也沒差
return 1
if fib[x] != 0: # 若曾經算過，可以直接回傳答案（這邊用是否為 0 判斷）
return fib[x]
fib[x] = fibonacci(x-1) + fibonacci(x-2) # 狀態轉移公式
return fib[x]跟前面的 for loop 寫法的版本，幾乎就只是”換句話說”而已，是可以完全一比一的對應抄上去的。差別就是
- 寫 for loop 時，我們可以順著把結果一路放到記錄器裡面。
- 寫 recursion 時，是先確認該位置是否算過，若沒有，再依靠 recursion 得到答案，並把答案寫進記錄器。
無論如何，你的記錄器最終會寫滿過程中所有暫存的答案，也就成了我們前面一直提到的查詢表。
[Python 語法小教室] 這邊特別提一下，如果寫的是 Python，我們有更簡潔的寫法，只要加個 cache decorator 就能達到一樣的效果。
from functools import cache
@cache
def fibonacci(x): # x >= 0
if x == 0 or x == 1:
return 1
return fibonacci(x-1) + fibonacci(x-2)或許會在一些題解看到這個寫法，但你要知道他背後做了什麼，若不確定就別用，新手先採用更樸實無華的做法才是掌握正確觀念的最好方式。
那說到底，為何我們需要多一個記錄器，讓程式變得更囉唆？因為如果說遞迴其中一種精神就是
可以靠較小問題的答案，去解答較大的問題，而且解決方法都是一樣的
那動態規劃，就是在此之上，再多一件事而已，那就是
這些小問題的答案，會重複被用到
就是這個重複，體現了動態規劃的精髓。舉個例子，以費氏數列來說
- 你算 f(5) 的時候需要先知道 f(4) 跟 f(3)
- 但你算 f(6) 的時候需要先知道 f(5) 跟 f(4)
這邊 f(4) 就被重複使用了，不要小看這小小的重複一次，假如你都不記下來，每次都重算，全部累積起來，會讓你的時間複雜度變成 O(2＾N)。但一旦我們有先把曾經算過的答案存起來，時間複雜度就可以變成 O(N)。
而這個”把算過的小問題的答案存起來並重複使用”的動作（其實也就是 Cache 的概念），就是整個動態規劃演算法的精髓，也是這整篇提到的查詢表真正的由來。
那，我們現在同一題有了兩種寫法，有什麼差嗎？本質上他們幾乎是完全等價的，也就是說，你用哪個都行。
- 用迴圈 for loop ，有個專有名稱叫做 bottom-up，因為他從 index 小的往大的走。
- 用遞迴 recursion 做的，則叫做 top-down，因為他是從 index 最大的開始遞迴。
不管用哪個，最終你得到的東西都一樣，就是那個查詢表，然後回傳要問的某個特定點的值。他們之間通常也可以無痛翻譯。
但如果是新手，一定想先學一種的話，學哪個比較好？我自己是建議。
- 沒有特別偏好，那先學好 bottom up。
- 若你很熟悉遞迴思維，覺得 top down 更直覺，那先學他也無妨。
總之觀念先打穩最重要，熟練以後，再去想另一個怎麼翻譯是很容易的事。然後很多問題，你去網路上找解答，往往只會看到其中一種版本，所以你也需要懂得自己翻譯成另一個版本。總的來說，這兩個不會差太多，時間複雜度是一樣的，程式碼的核心部分也會很相似。
不過 bottom up 對初學者來說還有個很巨大的額外好處，就是很直觀的能理解他的時間複雜度，光看有幾個 for loop 就知道了對吧。所以這系列我會以 bottom up 為主去寫 Sample Code，但若你有看懂，應該有辦法把他”翻譯”成 top down，也可以當成一種自我練習。
註: 硬要說兩者的優缺點還是有的，但大多體現在更艱深的問題。舉例來說，有些困難的問題會進入到數學優化的世界，也就是轉移方程式很繁複，寫完後還得要經過多道手續重新調整，此時 bottom up 的寫法，會讓你稍微更好想一點。（參考搜尋關鍵字：狀態壓縮、DP 優化）。
而 top down 則在某些特殊時候有優勢，也就是你可能不用真的把”每一個子問題全都解出來”的情況，例如你遞迴的過程可能是跳步的，那 bottom up 一定從小到大，他沒辦法知道哪些要跳過。但 top down 從大到小，走的過程中沒走到的路，就是自然跳掉了，但一般來說若僅看 worst case 就差別不大。
總結
最後，讓我們統整一下，這一整篇的重點
1. 找到合適的狀態定義
動態規劃的結果，通常是做出一張查詢表
如果你能想到一組 key-value 的查詢表，可以協助你回答問題，那這組 key-value 就是你的狀態函數 f(key) = value。
2. 找到狀態間轉移的公式
有狀態函數還不夠，他們必須要有可以轉移的關係存在，某幾個狀態，透過一些組合計算，可以算出其他的狀態。然後這個轉移公式又不會簡單到讓你直接能靠數學方式一口氣算出最終答案，只能老實的一個一個算出來。
3. 初始值是什麼
如果以上都順利，最後要好好確定，你需要怎樣初始值，也可以說是初始條件，可以讓這個狀態轉移公式啟動，最終算出你原本想要的答案。
而這個過程，其實跟遞迴的思路是很相似的，但你未必要用遞迴去寫。bottom-up 與 top-down 兩種寫法，沒有一定限制，都沒偏好的話，其實選 bottom-up 會比較簡潔好懂。
最後，幾乎所有動態規劃題目，核心的程式碼就是這樣幾行而已。
Bottom-Up
def calculate(n: int):
arr = [0] * (n + 1) # 初始化：開一個足夠長度的陣列，通常可以用 0
arr[0] = xxx # 設定初始值，通常是 index = 0 的位置
for i in range(1, n + 1):
arr[i] = ... # 狀態轉移公式，通常是由一個或數個之前的狀態 arr[i-?] 組成
return arr[n] # 回傳第 n 個位置的值Top-Down
arr = [0] * (n + 1) # 初始化：開一個足夠長度的陣列
def calculate(i: int):
if i == ...: # 初始值的位置
return ... # 回傳初始值
if arr[i] ... : # 判斷是否已經算過，不用重算
return arr[i] # 回傳之前暫存起來的答案
arr[i] = ... # 狀態轉移公式，用遞迴去計算
return arr[i]到這邊，講完了!
… 嗎？
當然不是，這只是開始而已。實際上，雖然要關注的就少少幾件事，但他們各自可以千變萬化，這才是動態規劃真正讓新手感到絕望的原因，太多種變化了，如果不是像費式數列這麼直白的例子，我哪知道狀態定義是什麼？轉移式又是什麼？每次看解答，都覺得我哪可能猜的到？要我通靈嗎？
不用緊張，這系列就是來幫助你的！第一篇先讓我們牢牢掌握著核心精神就好！
事實上，較為簡單的問題，通常給的輸入就是 key，要的答案就是 value，照抄下來就是狀態定義了。例如費氏數列問題是，問你數列上的某個位置的值是多少。那此時位置就是 key，費氏數列的值就是 value。
那你剩下唯一要想的部分只有第二點，如何轉移，把轉移公式寫出來，問題就差不多做完了。
然後對於轉移公式，簡單的問題，幾乎都是 f(x) = a * f(x-p) + b * f(x-q) + c 這種線性的組合，也就是用往前的少數幾個狀態，經過一些湊合，就可以算出現在的狀態，常見型態也不多，花點時間就能習慣。
下一篇，我們就將要拿幾個簡單的實際例子來練習，沒有費式數列這麼無腦，但也幾乎都是問題敘述裡面就能找出狀態定義，然後花一點心思就能看出狀態轉移的方式，期望讀者看的時候，都可以先試著自己想想看再看後面解說。
PS: 最後額外補充一下，事實上，要找費氏數列的值還真的有比動態規劃更高效的做法，但方法比較特殊且複雜，也跟動態規劃無關，所以就不會在這系列中提了，有興趣的可以 Google 搜尋關鍵字 “矩陣快速冪”。
