# [資演] 動態規劃 (I): 動態規劃簡介
###### tags: `資演`

在正式進入動態規劃之前，我們先來看一個例子：計算fibonacci數列。以下是計算fibonacci數列的Python code：

def fib(n):
    if n < 0:
        return None
    
    if n == 0 or n == 1:
        return n
    
    return fib(n - 2) + fib(n - 1)

現在考慮計算`fib(5)`，遞迴的相依關係可以繪製成下圖，也就是遞迴樹：

我們可以看到，`fib(0)`到`fib(3)`都出現了複數次，也就是說，出現了重複計算的情形，浪費了計算時間。有沒有辦法可以將這個計算結果儲存下來，這樣就不用重複計算，節省一些時間呢？我們把code改寫如下：

def fib(n):
    if n < 0:
        return None
    
    if n in [0, 1]:
        return n
    
    dp = [0 for _ in range(n + 1)]
    dp[0] = 0
    dp[1] = 1
    
    for i in range(2, n + 1):
        dp[i] = dp[i - 2] + dp[i - 1]
        
    return dp[n]

這邊我們用到的就是稱為**動態規劃**（dynamic programming）的技巧，其中`dp`稱為動態規劃陣列。

## 動態規劃是什麼？
動態規劃是分治法（divide and conquer）的一個優化方式。當分治法分割出來的問題，一而再、再而三出現，就建立一個表格來儲存這些問題的答案，避免重複求解，以空間換取時間。

我們跟著[這篇文章](https://www.zhihu.com/question/23995189)的思路來一步一步解構動態規劃。

### 湊硬幣問題
這是一個LeetCode上的題目：[322. Coin Change (Medium)](https://leetcode.com/problems/coin-change/)。

假設你身上帶了足夠的不同面額的的硬幣。現在的目標是湊出某個金額 $w$，希望用到盡量少的硬幣。我們想求出最少需要幾個硬幣。如果湊不出目標的金額，回傳`-1`。

舉例來說，我們現在有1、5、10、20、50、100這幾種硬幣。依據生活經驗，我們可以想到一個簡單的策略：能用100的就盡量用100的，否則盡量用50的......依次類推。這種策略稱為**貪心（greedy）策略**，在某些時候是可以使用的。貪心策略會盡快讓需要湊出的金額 $w$ 變得更小。能讓 $w$ 少100就盡量讓它少100，這樣我們接下來面對的問題就是湊出 $w-100$。對於現在這組面額，貪心策略可以運作，然而如果換了一組面額呢？假設某個奇葩的國家把硬幣的面額換成1、5、11，如果我們想湊出15元，貪心策略會給出這樣的結果：
$$
15=1\times11+4\times1 ~~~~~~ \Rightarrow 貪心策略需要用到5枚硬幣
$$然而，正確的最少硬幣解為
$$
15 = 3 \times 5 ~~~~~~ \Rightarrow 只需要3枚硬幣
$$為什麼會這樣呢？貪心策略錯在了哪裡？

剛剛已經說過，貪心策略的核心概念是：盡量使接下來面對的w更小。這樣，貪心策略在 $w=15$ 的情形時，會優先使用11來把 $w$ 降到4；但是在這個問題中，湊出4的代價是很高的，必須使用四個1元。如果使用了5元硬幣，$w$會降為10，雖然沒有4那麼小，但是湊出10只需要兩個5元。　　

在這裡我們發現，貪心是一種只考慮眼前情況的策略。也就是說，**短視近利**。

那麼我們要怎樣才能避免短視近利造成的問題呢？

第一個方法是暴力解。如果直接暴力窮舉出所有可以湊出 $w$ 的方案，明顯複雜度過高。太多種方法可以湊出 $w$ 了，窮舉它們需要的時間太多。

重新檢視一下剛才的例子，當 $w=15$ 時，我們如果先取11元硬幣，接下來就面對 $w=4$ 的情況；如果先取5元硬幣，則接下來面對的是 $w=10$ 的情況。我們發現這些問題都有相同的形式：**給定 $w$，湊出 $w$ 所需的最小硬幣數量是多少？**

接下來，我們用 $f(n)$ 來表示「湊出 $n$ 元所需的**最少**硬幣數量」，用 $\text{cost}$ 來表示「按照目前策略湊出 $n$ 元消耗的硬幣數量」。

現在要湊出15元，我們先選擇了11元硬幣，故有：
$$
\text{cost} = f(4) + 1 = 4+1 = 5
$$它的意義是：使用現在的策略，付出的代價等於 $f(4)$ 加上自己這枚硬幣。現在我們暫時不管f(4)怎麼求出來。另一方面，如果我們用5來湊出15，則：
$$
\text{cost} = f(10) + 1 = 2+1 = 3
$$那麼，現在$w=15$的時候，我們該取那種硬幣呢？當然是各種方案中，cost值最低的那一個！

我們在這三種硬幣中做出一個**選擇**，這個選擇使得目前面對的$w$發生變化，也就是所謂的**狀態轉移**。$f(n)$ 只與 $f(n - 1), f(n - 5), f(n - 11)$ 相關；更確切地說：
我們要求出 $f(n)$，只需要求出幾個更小的 $f$ 值；既然如此，我們從小到大把所有的 $f$ 求出來不就好了？注意一下邊界情況即可。我們把這個簡單的邏輯寫成Python code：

# 先把硬幣數量初始化成一個不可能的硬幣數量
# 例如無限大，或是總金額 + 1（因為硬幣最小就是 1 元）
# 這裡初始化為 15 + 1 = 16
dp = [16 for _ in range(16)]
dp[0] = 0

for i in range(1, 16):
    cost = 16
    if i >= 1:
        cost = min(dp[i - 1] + 1, cost)
    if i >= 5:
        cost = min(dp[i - 5] + 1, cost)   
    if i >= 11:
        cost = min(dp[i - 11] + 1, cost) 
    dp[i] = cost

最後得到`dp[15]`就是所需要的答案。

我們也可以很容易地推廣到任意硬幣種類的情形：現在硬幣共有`coins`裡面給定的幾種面額，要湊出的金額是`w`。按照上面的邏輯，寫出的Python code如下：

class Solution:
    def coinChange(self, coins: List[int], w: int) -> int:
        dp = [(w + 1) for _ in range(w + 1)] 
        dp[0] = 0
        for i in range(1, w + 1):
            cost = w + 1
            for c in coins:
                if i >= c:
                    cost = min(dp[i - c] + 1, cost)
            dp[i] = cost      
        return dp[w] if dp[w] != w + 1 else -1

### 切鋼條問題
這是一個教科書上的經典問題：給定長度為 $n$ 的鋼條，把它切成一小段一小段再拿去賣（每段長度皆為整數），不同長度的小鋼條價格不一樣，對應的價格為一陣列 $p$，求最多可以賣到多少錢，以及可以賣到最多錢的切法。若現在 $n = 4$，且我們有：
總共有以下幾種可能的切分法（標在上面的數字是價格）：
在每個整數長度的地方可以選擇切或不切（除了頭和尾以外），因此可能的切法有 $2^{n - 1}$ 種，也就是說，複雜度為指數複雜度，當 $n$ 很大的時候會非常耗時。幸好，可以使用動態規劃解決這個問題。

把一個鋼條切成 $k$ 個小段，長度分別為 $i_1, i_2,\dots, i_k$，並且滿足：
$$
n = i_1 + i_2 + \dots + i_k
$$這些小段的價格加起來就是總共得到的收益：
$$
r_n = p_{i_1} + p_{i_2} + \dots + p_{i_k}
$$可以這樣思考這個問題：當切掉一段鋼條時，剩下的鋼條必須也是被最佳分段的，這樣全部的鋼條才能夠被最佳分段。這就是所謂的**最佳子結構**：不斷地把問題變成更小的子問題，再去解決這些子問題（divide and conquer）。因此，我們可以寫出如下式的遞迴關係：
$$
r_n = \max(p_n, r_{n - 1} + p_1, r_{n - 2} + p_2, \dots, r_1 + p_{n - 1})
$$其中，第一項代表不切割直接整條拿去賣；第二項代表切掉一塊長度為 1 的鋼條（價值為 $p_1$），再將剩下的鋼條最佳切分（價值為 $r_{n-1}$）；第三項代表切掉一塊長度為 2 的鋼條（價值為 $p_2$），再將剩下的鋼條最佳切分（價值為 $r_{n-2}$），以此類推。

以下分別介紹動態規劃的兩種做法：top-down with memoization 以及 bottom-up。

#### Top-down with memoization
這個方法是遞迴的直覺優化：一樣按照遞迴的呼叫順序來解決問題，只是對於同一個問題只解一次，並把結果儲存下來（這個動作稱為memoization），之後再遇到相同的問題就可以直接存取並回傳之前計算好的結果。

def memoized_cut_rod(p, n):
    # 初始化 memo 陣列，總共有 memo[0] 到 memo[n]
    # memo[0] = 0 （長度為 0 的鋼條賣不到錢）
    # 其他元素設成 -1
    memo = [-1 for i in range(n + 1)]
    memo[0] = 0
    return memoized_cut_rod_aux(p, n, memo)

def memoized_cut_rod_aux(p, n, memo):
    # 如果所求的值尚未被算出來，也就是該元素仍為 -1
    # 我們就必須替這個 n 計算求解
    if memo[n] == -1:
        value = -1
        for i in range(1, n + 1):
            # 把解填入 memo
            value = max(value, p[i] + memoized_cut_rod_aux(p, n - i, memo))
        memo[n] = value
    return memo[n]

#### Bottom-up
一般提到動態規劃，指的通常是這種方式：先建立一個空表格，依序將計算結果填入表格，再由前面已填入的值計算後面的表格值，最終得到題目要求的結果。這種方法雖然複雜度的數量級和top-down相同，但通常有著較小的常數factor；也因為子問題依照一定的順序求解，通常可以進行空間優化。

def bottom_up_cut_rod(p, n):
    # 初始化 dp 陣列，總共有 dp[0] 到 dp[n]
    # dp[0] = 0 （長度為 0 的鋼條賣不到錢）
    # 其他元素設成 -1
    dp = [-1 for i in range(n + 1)]
    dp[0] = 0
    
    # 把解填入 dp 陣列
    for j in range(1, n + 1):
        value = -1
        for i in range(1, j + 1):
            value = max(value, p[i] + dp[j - i])
        dp[j] = value
    return dp[n]

#### 如何建構出賣到最多錢的解？
現在得到了可以賣的最高價格，但不知道要怎麼切才能賣到那個價格，怎麼辦？

可以對原本的`bottom_up_cut_rod`稍作修改，加入一個長度也是 $n+1$ 的陣列`s`，其中`s`的第 $i$ 個元素代表長度為 $i$ 時，最佳的一刀切法所需要切掉的長度。我們將`bottom_up_cut_rod`修改為下面的`extended_bottom_up_cut_rod`，回傳兩個陣列`dp`和`s`：

def extended_bottom_up_cut_rod(p, n):
    dp = [-1 for i in range(n + 1)]
    s = [-1 for i in range(n + 1)]
    dp[0] = 0
    for j in range(1, n + 1):
        value = -1
        for i in range(1, j + 1):
            if value < p[i] + dp[j - i]:
                value = max(value, p[i] + dp[j - i])
                s[j] = i
        dp[j] = value
    return dp, s

若要印出整根鋼條最佳的切分法，可以這樣做：

_, s = extended_bottom_up_cut_rod(p, n)
while n > 0:
    print(s[n])
    n = n - s[n]