Learning Objectives
- 寫出 0/1 背包的狀態與轉移式，追蹤二維表格怎麼填，並從表格還原選了哪些物品
- 說明 0/1 背包改用一維陣列時，容量為什麼要由大到小
- 寫出最長共同子序列（LCS）的轉移式，並從表格還原出子序列
- 寫出編輯距離的轉移式，說明插入、刪除、取代各對應表格的哪一格
- 分辨子序列與子字串，並估計這些演算法的時間與空間複雜度
三個用二維表格解的問題
上一課的爬樓梯和找零，狀態只要一個數字（第幾階、幾元）。這一課的三個問題，狀態需要兩個數字，表格變成二維：
| 問題 | 生活裡的例子 | 狀態 dp[i][j] |
|---|---|---|
| 0/1 背包 | 行李限重，挑出總價值最高的東西 | 只考慮前 i 件物品、容量 j 時的最大價值 |
| 最長共同子序列（LCS） | 比對兩份文件哪些內容相同（diff） |
兩個字串各取前 i、前 j 個字時的答案 |
| 編輯距離 | 拼字檢查建議最接近的單字 | 把前 i 個字變成前 j 個字最少要幾步 |
做法都一樣：定義狀態、寫出轉移式、設定第 0 列與第 0 行的初始值、由左上往右下填表。 最後的答案在右下角，而從右下角往回走，就能還原出最佳解實際的選法。
0/1 背包：每件拿或不拿
背包容量 7，有四件物品，每件只能整件拿或不拿：
| 物品 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 重量 | 1 | 3 | 4 | 5 |
| 價值 | 1 | 4 | 5 | 7 |
第 20 課的貪婪法（每單位重量價值高的先拿）會先拿物品 4（7 ÷ 5 最高），剩下容量 2 只放得下物品 1，總價值 8。 最好的選法其實是物品 2、3，重量剛好 7，價值 9。
狀態：dp[i][w] 是「只考慮前 i 件物品、背包容量 w」時能拿到的最大價值。
轉移式：看第 i 件物品（重量 wt[i-1]、價值 val[i-1]，陣列從 0 開始所以減 1）：
- 不拿它：價值和只考慮前 i - 1 件一樣，
dp[i - 1][w] - 拿它（裝得下時）：先留出它的重量，剩下的容量給前 i - 1 件，
dp[i - 1][w - wt[i-1]] + val[i-1]
dp[i][w] 取兩者比較大的。初始值：第 0 列（一件都不考慮）全部是 0。
還原：從右下角 dp[4][7] 開始。如果 dp[i][w] 和正上方 dp[i - 1][w] 一樣，表示第 i 件沒拿也能得到這個價值，往上走；
不一樣，表示第 i 件有拿，記下來，容量扣掉它的重量再往上走。
時間與空間都是 O(n × W)。
0/1 背包：填表與還原
表格一列一列填：每一格先抄正上方（不拿），再看「留出這件的重量、往上一列找剩下容量的答案、加上它的價值」會不會更大。填完後，框框從右下角往上走：第 4 列和第 3 列一樣（沒拿第 4 件），第 3 列和第 2 列不同（拿了第 3 件），容量剩 3，再到第 2 列……最後還原出拿了第 3、2 件。
只用一列：容量要由大到小
仔細看轉移式，第 i 列只用到第 i - 1 列。所以不必存整張表，用一個一維陣列 dp[w] 反覆更新就好，空間從 O(n × W) 降到 O(W)：
for w in range(W, wi - 1, -1): # 由大到小
dp[w] = max(dp[w], dp[w - wi] + vi)
關鍵在容量由大到小。更新 dp[w] 時要用的 dp[w - wi] 必須還是「上一列」（還沒考慮這件物品）的值。
由大到小算，dp[w - wi] 在比較小的位置，這一輪還沒被改過，正好是上一列的值。
如果改成由小到大，dp[w - wi] 可能已經在這一輪放過這件物品，等於同一件物品被拿了兩次以上。
那其實是另一個問題：每件物品可以拿無限多次的「無限背包」，它反而就要由小到大。
一維陣列的 0/1 背包
每處理一件物品，▲ w 從右往左掃，▲ w-wi 指著它要參考的格子；那一格在左邊，這一輪還沒被改過。處理完四件物品，dp 就等於上一個範例表格的最後一列，dp[7] 是 9。
想一想：0/1 背包
重量 [2, 3, 4]、價值 [3, 4, 5]、容量 5，0/1 背包的最大價值是多少？
dp[i][w] 和正上方的 dp[i - 1][w] 相同，代表什麼？
一維陣列的 0/1 背包，如果把內層迴圈改成容量由小到大，會發生什麼事？
最長共同子序列（LCS）
子序列（subsequence）是從字串裡刪掉一些字（也可以不刪），剩下的字保持原來的順序；不需要連在一起。
例如 BCB 是 ABCBD 的子序列。要求連在一起的叫子字串（substring），兩者不要混淆。
兩個字串都有的子序列裡最長的，叫最長共同子序列（longest common subsequence，LCS）。版本控制工具比對兩份檔案哪些行沒變、 生物資訊比對兩段 DNA，都用到這個想法。
狀態：dp[i][j] 是 a 的前 i 個字和 b 的前 j 個字的 LCS 長度。
轉移式：看兩邊的最後一個字 a[i-1]、b[j-1]：
- 相同：這個字可以接在兩邊都少一個字的 LCS 後面，
dp[i][j] = dp[i - 1][j - 1] + 1（左上角加 1） - 不同：兩個字不可能同時用上，至少丟掉一個：
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])（上面和左邊取大的）
初始值：第 0 列和第 0 行是空字串，LCS 長度是 0。
還原：從右下角開始，字相同就把這個字收下、往左上走；不同就往上面和左邊比較大的那格走。收集到的字是倒著的，最後反轉。 相同大的時候固定往上走，三種語言才會還原出同一個子序列（LCS 可能不只一個）。
時間與空間都是 O(n × m)。
LCS：填表與還原子序列
列標題是 a = ABCBD 的每個字，欄標題是 b = BDCAB 的每個字。兩個字相同的格子是左上角加 1，不同的格子取上面和左邊比較大的。填完後框框從右下角往回走，遇到相同的字就往左上走並收下那個字，最後得到 BCB。
編輯距離：最少要改幾步
把一個字串變成另一個字串，每一步可以插入一個字、刪除一個字，或把一個字取代成另一個字。最少要幾步？ 這個步數叫編輯距離（edit distance，也叫 Levenshtein 距離）。拼字檢查會建議和你打錯的字編輯距離最小的單字。
例如 horse 變成 ros：把 h 取代成 r（rorse），刪掉第二個 r（rose），刪掉 e（ros），共 3 步。
狀態：dp[i][j] 是把 a 的前 i 個字變成 b 的前 j 個字，最少要幾步。
轉移式：看兩邊的最後一個字：
- 相同：不用動它，
dp[i][j] = dp[i - 1][j - 1] - 不同：最後一步有三種可能，取最少的再加 1：
| 最後一步 | 意思 | 參考的格子 |
|---|---|---|
| 刪除 | 刪掉 a 的最後一個字，剩下 a 的前 i - 1 個字要變成 b 的前 j 個字 | 上面 dp[i - 1][j] |
| 插入 | 先把 a 的前 i 個字變成 b 的前 j - 1 個字，再插入 b 的最後一個字 | 左邊 dp[i][j - 1] |
| 取代 | 把 a 的最後一個字換成 b 的最後一個字 | 左上 dp[i - 1][j - 1] |
初始值：dp[i][0] = i（全部刪掉）、dp[0][j] = j（全部插入）。時間與空間都是 O(n × m)。
編輯距離：horse 變成 ros
先填第 0 行（全部刪掉）和第 0 列（全部插入），再一列一列填。字相同的格子直接抄左上角；不同的格子是上面、左邊、左上三格最小的再加 1。右下角是 3。
想一想：LCS 與編輯距離
ABCD 和 ACBD 的最長共同子序列長度是多少？
sunday 變成 saturday 的編輯距離是多少？
ACE 是 ABCDE 的子序列嗎？是它的子字串嗎？
實作：算出 LCS 的長度
請完成 lcs_length 的轉移式，算出三組字串的最長共同子序列長度。第三組沒有任何相同的字，答案是 0。
重點整理
| 問題 | 狀態 | 轉移式 | 複雜度 |
|---|---|---|---|
| 0/1 背包 | dp[i][w] 前 i 件、容量 w 的最大價值 |
max(dp[i-1][w], dp[i-1][w-wt] + val) |
O(n × W) |
| LCS | dp[i][j] 前 i 個字與前 j 個字的 LCS 長度 |
相同：左上 + 1；不同：max(上, 左) |
O(n × m) |
| 編輯距離 | dp[i][j] 前 i 個字變成前 j 個字的最少步數 |
相同：左上；不同：1 + min(上, 左, 左上) |
O(n × m) |
- 從右下角往回走，依每一格是從哪裡來的，就能還原出最佳解
- 0/1 背包只用一維陣列時，容量要由大到小，否則同一件物品會被拿很多次
- 子序列不必相連，子字串必須相連
下一課：回溯法。動態規劃把子問題的答案記下來；回溯法則是一步一步試，走不通就退回上一步換別的選擇，用在排列、子集合、N 皇后這類要列出所有可能的問題。