我們在定義狀態的時候，可以把目前資料的數值當作狀態的其中一個維度。在建立維度的時候，必須要小心數字的範圍，否則可能會造成無窮遞迴、或者是狀態總數過於龐大。其實這類動態規劃我們在第一天的費氏數列和找零錢問題就看到了～今天來多講一些經典例子吧！比方說背包問題！

背包問題 Knapsack Problem

背包問題是這樣的：有 N 樣物品，第 i 樣的重量是 w[i]、其變賣可得的價值為 v[i]。現在你是一個小偷，你帶了一個承載重量上限為 W 的背包。請問你能不能選一些物品放進去，使得整個背包的總價值最高呢？

從數學的角度來說，假設我們把裝進背包的物品編號蒐集起來，寫作集合 X。那麼我們的目標函數就是

若我們將注意力集中在某一個特定物品上——比方說最後一個重量是 w[n]、價值是 v[n] 的物品。如果我們要把它放進背包，那麼這個背包承重上限就從 W 掉到 W-w[n] 了。若沒有打算把它放到背包，那麼背包承重上限仍是 W 不變。無論發生哪一種情形，接下來需要考慮裝載的物品、其範圍從 1 到 n 變成了 1 到 n-1 的物品。

從以上的觀察，我們可以發現：如果所有物品的重量都是正整數，那麼我們就能夠把「目前的背包承重上限」與「物品選擇的範圍」定義為狀態的兩個維度！利用「選」或「不選」第 n 個物品的分歧條件，得到其遞迴關係如下：

備註：對某些人來說「選」或「不選」是個很難的問題，就跟動態規劃一樣！小朋友才作選擇，所以當然要兩種情況都考慮看看～

Exercise 19: Leetcode 474 - Ones and Zeroes

題目連結

https://leetcode.com/problems/ones-and-zeroes/

題目敘述

給你一個陣列的 K 個二元字串(K ≤ 600，每個字串都是由 0 和 1 兩種字元構成)。我們現在想要從中選一些字串出來，使得這些字串中的 0 的數量最多只用 m 個、而 1 的數量最多只用 n 個。請問最多可選多少個字串呢？

解題思考

在這個問題中，m 與 n 的值代表了背包中兩種資源的承載上限，所以我們可以用 dp((m, n), K) 定義我們的背包狀態～對於隨邊拿到手上的一個字串，假設它有 i 個 0 和 j 個 1，此時我們根據選或不選的兩種策略，可以找出對應的子問題：

顯然邊界條件就是當 K = 0 的時候，怎麼湊都沒有字串，所以 dp(任意值, 0) = 0。列出了這個遞迴關係後，可以很直接地用遞回來寫，不用擔心更新順序！

參考程式碼 (Python3)

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dp = {}
        arr = [[s.count('0'), s.count('1')] for s in strs]
        def solve(m, n, k):
            # 邊界終止條件
            if k == 0:
                return 0
            # 判斷這個狀態是否已經計算過了
            if dp.get(((m, n), k)) != None:
                return dp[((m, n), k)]
            # 考慮不拿走這個物品的情形
            maxstrings = solve(m, n, k-1)
            # 如果在背包重量上限範圍內，才考慮拿走這個物品
            if arr[k-1][0] <= m and arr[k-1][1] <= n:
                maxstrings = max(maxstrings,
                                        1 + solve(m - arr[k-1][0], n - arr[k-1][1], k - 1))
            # 記得把算好的結果存進去
            dp[((m, n), k)] = maxstrings
            return maxstrings
        return solve(m, n, len(arr))

Exercise 20: Leetcode 903 - Valid Permutations for DI Sequence

題目連結

https://leetcode.com/problems/valid-permutations-for-di-sequence/

題目敘述

給你一個長度為 n、由 D 和 I 組成的字串 S[0..n-1]，請計算有多少 0~n （總共 n+1 個數字）的排列 P[0..n] 會滿足：如果 S[i] 是 D，那麼 P[i] > P[i+1]（代表遞減）、如果 S[i] 是 I，那麼 P[i] < P[i+1]（代表遞增）。請輸出答案除以 1e9+7 的餘數。

解題思考

我們可以研究看看最後一個字元發生什麼事情。如果最後一個字元是 D，那麼 P[n] 得要比 P[n-1] 來得小。舉例來說：比方說 (2,0,1,4,5,3) 的最後一個字元可以是 D。在這種情況下，拿掉最後一個數字會發生什麼事情？(2,0,1,4,5,3) → (2,0,1,4,5) 就不是一個合法的 0~n-1 排列了！但好加在，我們發現 D 與 I 的關聯、跟數值本身沒什麼關係，所以我們可以把 (2,0,1,4,5) 把大於 3 的數字全部 -1，重新寫成 (2,0,1,3,4)。這個操作是可以反向進行的，如果我們拿到了 (2,0,1,3,4)，在已知最後一個數字 = 3 的情況下，保證可以做出 (2,0,1,4,5,3) 這個數列、並且不改變大小關係。

根據上面的情報，我們覺得「把最後一個數字的數值」加入狀態，或許是個不錯的選擇！

於是，我們就可以定義 dp(i, x) = 考慮 0~i 的排列，滿足前 i 個字元並且最後一個數字是 x (0 ≤ x ≤ i) 的方法數有幾種。比方說上面這個 (2, 0, 1, 4, 5, 3) 的例子，排列是 0~5 所以 i = 5、最後結束在 x = 3，會被計算在 dp(5, 3)。那麼這個狀態可以從哪些前綴得到呢？由於最後一個字元是 D，所以能夠接在 3 前面的只能是 4 或 5。但是因為少了一位數之後，所有比 3 大的數字都減一了，因此我們要找的是 dp(4, 4-1) 與 dp(4, 5-1)，也就是 dp(4, 3) + dp(4, 4)。（0~4 的排列且結束在 3 ；或是 0~4 的排列且結束在 4）。於是就可以正式地寫遞迴式啦：

再拜託大家看看參考程式碼，依照更新順序我們可以把中間的 "..." 計算部分平均分攤處理掉變成 O(1) 時間唷。

參考程式碼 (Python3)

from collections import defaultdict

class Solution:
    def numPermsDISequence(self, S: str) -> int:
        MOD = int(1e9+7)
        n = len(S)
        dp = defaultdict(lambda: 0)
        dp[(0, 0)] = 1
        for i in range(1, n+1):
            if S[i-1] == "D":
                for x in range(i-1, -1, -1):
                    dp[(i, x)] = (dp[(i, x+1)] + dp[(i-1, x)]) % MOD
            if S[i-1] == "I":
                for x in range(1, i+1):
                    dp[(i, x)] = (dp[(i, x-1)] + dp[(i-1, x-1)]) % MOD

        return sum([dp[(n, x)] for x in range(0, n+1)]) % MOD

備註

為什麼是 1e9+7 呢？1000000007 這個數字其實是個質數唷！質數對於整數運算其實有相當大的好處（比方說我們可以嚴謹地定義除法之類的），再加上這個數字相當好記，足夠大又不超過 2^31-1，可以被 32 位元有號整數儲存下來。在 mod 1e9+7 的情形下，計算乘法就不需要用 BigInteger 了。另一個傳統上常見的質數是 1e6+3。在比賽中如果你看到某些質數如 998244353、167772161 之類的，那很可能與整數快速傅利葉轉換有關，其他質數可參考這篇博客。