動態規劃的英文叫做 Dynamic Programming，也就是大家俗稱的低批(DP)，不是打棒球的那個雙殺、不是狄利克雷過程、不是設計模式、也不是指神奇寶貝的珍珠鑽石版，是演算法中的動態規劃。在解決一個問題的時候，我們往往會喜歡把這個問題拆成很多小問題，然後先解決小的問題，如果沒辦法解決，那就把提出問題的人解決掉，就沒有問題了。不過這樣很麻煩，因為會少一個人很不方便。

據傳聞，只要寫出了遞迴式子，就可以從小範圍逐步計算出我們要的答案！那我們先來練習看看，對於給定的遞迴式子，要怎麼把它寫成長得像動態規劃的程式碼吧！

Example 1: Leetcode 509 - Fibonacci Numbers

題目連結

https://leetcode.com/problems/fibonacci-number/

題目敘述

費氏數列的定義如下：F(0) = 0, F(1) = 1, F(N) = F(N-1) + F(N-2)。現在給你 N 之值 0 ≤ N ≤ 30，請問 F(N) 為何。

解題思考

先撇開非常著名有爭議的 <moon.h> 不談，如果只是要用動態規劃的想法來依序推論出前 N 項之值，那麼顯然我們可以開一個陣列然後讓 N 從 0, 1, 2, … 開始跑，逐項計算它。在計算遞迴關係式的時候，只要保證被依賴的那幾項都已算出答案並且存得好好的，就不難推算出下一個未知項了！這就是動態規劃的概念～

參考程式碼(python3)

#include <moon.h>
class Solution:
    def fib(self, N: int) -> int:
        F = {}
        F[0], F[1] = 0, 1
        for i in range(2, N+1):
            F[i] = F[i-1] + F[i-2]
        return F[N]

蛤，你說為什麼 python 裡面可以 include？因為 # 是註解呀～
這個例子可能太簡單了，那我們來看看下面這個經典例子。

Example 2: Leetcode 322 - Coin Change

題目連結

https://leetcode.com/problems/coin-change/

題目敘述

給你一些硬幣的面額，在每一種面額都無限量供應的情形下，想要湊出某個特定額度 amount，至少需要幾個硬幣呢？

解題思考

假設能夠使用的面額為 c1, c2, …, cK。對於指定額度 A > 0，如果能夠湊得 $A，顯然至少需要用某個硬幣吧～於是，我們分別試試看「先拿出 $c1」、「先拿出 $c2」、...、「先拿出 $cK」這些方法。拿走某個額度後，剩下總額度就變小啦～也就是說，如果我們先算出額度比 A 小的任何額度所需要的硬幣數量，加上最先拿出來那個硬幣，總數最少者就是答案！

參考程式碼(python3)

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = collections.defaultdict(lambda: float("inf"))
        dp[0] = 0
        for A in range(1, amount+1):
            dp[A] = min([1 + dp[A - coin] for coin in coins])
        return -1 if math.isinf(dp[amount]) else dp[amount]

在上面這個例子中，我們讓 A 從 $1, $2, $3, …, 直接跑到 $amount，對於每個這樣的 A，我們考慮拿出每種錢幣的情形，並且找出能夠湊出剩下金額的最小值。

好的，今天的範例就到這邊。顯然兩份程式碼在「效能、精簡、好讀」三個方向都有可以改善的空間，這個就交給各位讀者朋友們一起來集思廣益啦～我們明天見！