# AP325-Python 第6章 動態規劃
「每一個DP背後都有一個dag，DP需要dag指引方向，如同視障者需要dog。」(Dynamic programming, Bottom-up)
「設計DP以尋找遞迴式開始，以避免遞迴來完成，除非，除非你準備小抄。」(Dynamic programming, Top-down memoization)
---
這一章介紹動態規劃(Dynamic Programming, DP)。DP名字中Programming的意思是指「以表格紀錄」，而非現在常用的「寫程式」，所以DP的意思是以變動的表格來求解的方法。
DP的應用很廣，變化很多，在學術界也發展的很早，在程式競賽也用的非常多，並且有很多困難而精妙的(優化)方法。這本教材只限於一些常用的典型的題型，此外樹與圖的DP將放在後續討論樹的專章中，而不在本章中。
## 基本原理
### 基本思維與步驟
DP與分治有個相同之處，都是將問題劃分成子問題，再由子問題的解合併成最後的解，其中子問題是指相同問題比較小的輸入資料。所以，設計DP的方法從找出遞迴式開始，設計DP的演算法通常包含下面幾個步驟：
* 定義子問題。
* 找出問題與子問題之間的(遞迴)關係。
* 找出子問題的計算順序來避免以遞迴的方式進行計算。
如果沒有進行第三個步驟，而只是以遞迴的方式寫程式，就會變成與第一章相同的純遞迴方式，純遞迴往往會遭遇到非常大的效率問題，所以也可以說DP就是要改善純遞迴的效率問題的技術。我們先介紹兩個簡單的問題，以問題來舉例說明會比較清楚。
**問題一**：小朋友上樓梯，每步走一階或兩階，如果走到第$n$階有$f(n)$種走法，輸入$n$，計算$f(n)$。
例如$n=3$時，走法有$1+1+1=3$或$1+2=3$或$2+1=3$，一共3種，$f(n)=3$。
我們的問題是計算$f(n)$。定義子問題：對$i\le n$，$f(i)$表示走到第$i$階的走法數。接著要找出$f(n)$與子問題的遞迴關係，我們雖然沒辦法立刻寫出$f(n)$是多少，但是我們只要去想，走到第$n$階的最後一步一定是走了一階或兩階(沒有其他的可能)，而最後一步是一階與兩階的走法必然不同(沒有重複多算)。最後走一階的走法數就是抵達第$n-1$的走法數$f(n-1)$，而最後一步走兩階的走法數就是抵達第$n-2$階的走法數$f(n-2)$，因此，我們得到遞迴關係式$f(n)=f(n-1)+f(n-2)$，但是不要忘了以上推論是對於$n>2$時的狀況，遞迴的初始條件$f(1)$與$f(2)$要另外找，不難想一下就可以知道，所以完整的遞迴關係是：
$$
f(n) = \left\{
\begin{array}{ll}
n & \text{if } n<3 \\
f(n-1)+f(n-2) & \text{otherwise}
\end{array}
\right.
$$
如果直接依照遞迴寫程式，以下是這樣簡單的程式。
```python=
def f(n):
if n < 3: return n
return f(n-1)+f(n-2)
#
n = int(input())
print(f(n))
```
這個程式可以跑，只要你不要輸入太大的數字。如果輸入40大概會看到螢幕停頓一下就跑出來，輸入60的話肯定可以去喝杯咖啡再看看跑出來沒；如果輸入100，跑到你死了也跑不出來；如果輸入200，那到地球毀滅也跑不出來。
原因何在？這是一個純遞迴的程式，一個遞迴呼叫兩個，兩個就會呼叫四個，雖然$f(n-1)$與$f(n-2)$並不一樣，但它會接近2的$n$次方，確切的時間複雜度大概是$O(1.618^n)$。
我們來把它改成DP，所以要進行第三步驟：**找出子問題的計算順序來避免以遞迴的方式進行計算**。什麼樣的計算順序會讓我們可以不需要遞迴呢？原則上「只要讓遞迴式等號右邊出現的在左邊的之前先算，並且用表格把算過的記下來，就可以不需要遞迴了。」
以這一題為例，遞迴式$f(n)=f(n-1)+f(n-2)$，如果$n$從小往大算，算到$f(n)$的時候，$f(n-1)$與$f(n-2)$都已經算過了，所以只要當初算完的時候有記下來，那就可以直接從表格中取出$f(n-1)$與$f(n-2)$來相加得到$f(n)$，完全不需要用到遞迴。那麼如何用表格紀錄呢？這一題我們可以開一個列表 list $F[]$，以$F[i]$記錄$f(i)$的值，程式就變成一個簡單的迴圈，沿著我們的計算順序($n$從小到大)，逐步從表格中取出值，計算後存入表格，程式如下：
```python=
# ch6 stair, dp
n = int(input())
F = [0]*(n+1)
F[1] = 1; F[2] = 2
for i in range(3,n+1):
F[i] = F[i-1]+F[i-2]
print(F[n])
```
這個程式跑得很快，不過數字太大會溢位就是了，一般在考這一類題目的時候都要求輸出模某數的餘數。我們完成了一個DP算法的設計，看起來並不是太難。請再回想一下剛才走過的思維步驟：定義子問題、找遞迴關係、最後找計算順序與定義表格來避免遞迴。所以DP從遞迴開始，但以去除遞迴來完成，看來似乎有點難，但以這題來說又很簡單。
其實，對於大部分的題目，尋找計算順序與表格都很簡單，最常出現的計算順序就是像這一題：由小到大，而表格就是用遞迴的參數來直接定義。真正難的是遞迴關係式的尋找。
我們再來看一個例子。
**問題二**：有一個$m \times n$的矩形方格，從左上角的格子出發，要到達右下角的格子，每一步只能向右或向下移動一格，若不同的路徑有$g(m,n)$條，輸入$m$與$n$，計算$g(m,n)$。例如$g(2,3)=3$，如下圖。
我們的問題是計算$g(m,n)$。
定義子問題：以$g(i,j)$表示出發點走到$(i,j)$的走法數，以矩陣列與行的方式定義位置，出發點為$(1,1)$，終點是$(m,n)$。
接著要找出$g(i,j)$與子問題的遞迴關係，同樣的，我們不必立刻寫出$g(i,j)$是多少，只要去想，最後一步一定向右或向下，也就是前一個位置一定是$(i,j-1)$或$(i-1,j)$，而且這兩類走法必然不同(沒有重複多算)。根據定義，我們可以得到
$g(i,j)=g(i,j-1)+g(i-1,j)$ for $i>1$ and $j>1$；初始條件為
$g(i,j)=1$ for $i=1$ or $j=1$。
得到遞迴式之後直接寫遞迴程式就是純遞迴，程式如下，再一次，遞迴的程式非常沒有效率：
```python=
# ch6 grid, recursion
def grid(m, n):
if m==1 or n==1: return 1
return grid(m, n-1)+grid(m-1, n)
#
m,n = [int(x) for x in input().split()]
print(grid(m,n))
```
要把純遞迴改成DP，就要找計算順序，讓遞迴關係式右邊的出現在左邊的之前，本題的遞迴式為$g(i,j)=g(i,j-1)+g(i-1,j)$，簡單觀察可以得知，只要$i$與$j$都從小到大就可以滿足需要，所以我們可以採取「由上而下，由左而右」的順序，當然也可以「由左而右，由上而下」，甚至可以沿著$i+j$由小而大的斜線的順序，有點自找苦吃就是了。
至於表格，最直覺的方式就是將$g(i,j)$記錄在一個二維陣列$G[i][j]$中。以下是程式，跑得很快，時間複雜度是$O(mn)$，而遞迴版本的複雜度則是組合數$C(m+n-2, m-1)$，因為這一題的答案其實有數學解，是排列組合的題目。請不需要擔心數學解這件事，通常程式考試與競賽都不出有數學解的題目，以這題來說，只要將某些格子變成禁止通行或者做一些變化，就難以用數學的方式求解了，畢竟程式考試主要考的是程式技巧。
```python=
# ch6 grid, dp
m,n = [int(x) for x in input().split()]
G = [[0]*(n+1) for i in range(m+1)]
for i in range(1,m+1): G[i][1] = 1
for j in range(1,n+1): G[1][j] = 1
for i in range(2,m+1):
for j in range(2,n+1):
G[i][j] = G[i-1][j]+G[i][j-1]
#
print(G[m][n])
```
### 狀態轉移
DP子問題的遞迴關係式也有人稱為「狀態轉移」，這個名詞大概是從有限狀態機(數位電路設計)來的。子問題可以看成一個狀態，目前的狀態是根據之前的那些狀態，這樣的轉換關係就稱作狀態轉移，設計DP時，最重要的就是找出狀態轉移。之前我們將子問題看成「部分解」，所以是在找部分解與更小的解之間的關係，這兩個講法只是描述的方式不一樣，其實是同一回事，有的時候這樣想比較方便，有的時候那樣想比較直覺。
雖然我們要在下一章才會討論圖(graph)，但提到狀態轉移，用圖的術語比較好說明。我們說狀態A是狀態B的前置狀態(predecessor)，如果狀態B是由A轉移過來的，一個狀態可能有多個前置狀態，通常一個狀態的值是由它的前置狀態的值做某些計算得到。如果我們把每個狀態想像每一個點，若A是B的前置狀態，則由A畫一個箭頭指到B，我們會得到一個所謂的圖(graph)，這個圖就是這個DP的狀態轉換圖，在圖論上來說，它必然是個有方向但沒有環路的圖(directed acyclic graph, dag)，所謂環路是指從某點出發，沿著箭頭前進，最後又走到出發點。遞迴關係不會無限遞迴，所以必然沒有環路。我們來看看前面兩個簡單的問題的狀態轉移。
小朋友上樓梯問題的子問題是走到第$i$階，關係式$f(n)=f(n-1)+f(n-2)$，所以狀態圖如下，也就是每個狀態由它的前兩個狀態轉移而來。
第二個問題是方格圖的問題，遞迴式是：
$g(m,n)=g(m-1,n)+g(m,n-1)$，每一個格子是一個點(狀態)，前置狀態是他的左方與上方。
對於一個dag，我們一定可以將它的所有點排成某個順序，在此順序中，每個箭頭都由前往後指，也就是說，每個點的前置點都在它之前，這樣的順序稱為**拓樸順序(topological sort)**。我們的DP就是要沿著一個拓樸順序來進行。有件事情要提醒，本節說明的狀態轉移以及dag與拓樸順序，是方便思考用的，在DP解題時通常並不需要把它建出來，也就是建在心中就可以了，不必建在程式中。我們在第三章的P-3-1樹的高度的問題時，曾經講過利用queue找樹的bottom-up順序，那就是個拓樸順序，而那一題確實就是樹的DP。
### 分類與複雜度
題目的分類往往有很多種，主要看目的何在而分類，這裡我們以便於理解與學習來分類。一個DP如果狀態有$O(n^x)$而轉移式涉及$O(n^y)$個狀態，一般可稱為xDyD的DP，例如小朋友上樓梯是1D0D的，因為有$n$個要算，每次算$f(i)$只涉及2個$f(i-1)$與$f(i-2)$。
方格路徑的問題則是2D0D，因為有$n^2$(假設$m=n$)個要算，每次只需要2個(左方與上方)。當然也有一些DP不在這個分類中。
一個xDyD的DP，如果沒有優化，很明顯的，時間複雜度就是$O(n^{x+y})$，一般來說若$y=0$時比較簡單，因為遞迴式單純，而且遞迴式找出來時，程式就已經差不多寫完了，因為套個迴圈依序計算就是了。$y=1$的DP題目通常存在某種優化或需要某些資料結構幫忙，所以會比較難。下一節開始的題目分析，我們的會先介紹$y=0$，然後再介紹$y=1$的狀況。
### Top-down memoization
前面講到設計DP算法的步驟，基本上要先找出遞迴式，然後找出計算順序來避免遞迴。這算是標準的DP，也稱為Bottom-up的DP。另外有一種實現DP的方式是不找計算順序，直接依照遞迴式寫遞迴，但是因為一定要避免遞迴的重複計算，所以採取了一些步驟，這種實現的方式稱為top-down memoization的DP，其中memoization字典上應該沒有這個字，大概是為了這個技術自己創造的，這個字是由memo(備忘錄，便籤小紙條)變來的，這個方法基本上應該是打比賽或重實作的人上發展出來的(偷懶)方法，因為從理論的角度，除了程式比較好寫之外，這麼做沒有好處，但考試與比賽還真的就希望比較好寫。
用比較俏皮的講法，這個方法就是再找到遞迴式之後，直接寫成遞迴版本的程式，但要加上三個動作：
* 開一個表格當作小抄，用來記錄計算過的結果，表格初值設為某個不可能的值，用以辨識是否曾經算過。
* 在遞迴之前，先偷看一下小抄是否曾經算過，如果小抄上有答案(已經算過)，則直接回傳答案。
* 如果小抄上沒有，就遞迴呼叫，但計算完畢回傳前，要把它記在小抄上。
我們來看看前面介紹的兩個問題的遞迴版本如何改成top-down DP。下面是第一題，首先注意到它就是拿前面的遞迴版本來改的，修改的部分：第9行初始了一個表格$F[]$；在遞迴函數中第3行做了一個檢查是否$F[n]>0$的動作，如果是則直接回傳，這一題的數字都是正數，所以我們可以用0來表示沒算過；如果沒算過，第5行就真的遞迴呼叫去計算，然後存在表格中在回傳。
```python=
# ch6 stair, top-down dp
def f(n):
if F[n] > 0: return F[n]
if n < 3: return n
F[n] = f(n-1)+f(n-2)
return F[n]
#
n = int(input())
F = [0]*(n+1)
print(f(n))
```
這個”遞迴”的程式跑得慢不慢呢？基本上跟迴圈版的DP跑得一樣神速。我們再來看第二題方格路徑的改法。下面是修改版的程式，其實每一個top-down的DP幾乎都是長的這個樣子。這裡我們故意用了一些與上一題稍微不同的修改方式，雖然這題也可以用陣列初值為0表示沒算過，但我們自己寫陣列的初始化(設為-1)，因為有些題目可能有此需要。上一題我們把遞迴終點條件拿掉，替代以在主程式中設定起始點的表格值，這一題我們留著遞迴的終端條件，其實這些差異都不大。這個程式也是跑得跟DP版一樣的神速。
```python=
# ch6 grid, top-down dp
def grid(m, n):
if m==1 or n==1: return 1
if G[m][n]>0: return G[m][n]
G[m][n] = grid(m, n-1)+grid(m-1, n)
return G[m][n]
#
m,n = [int(x) for x in input().split()]
G = [[0]*(n+1) for i in range(m+1)] # memo
print(grid(m,n))
```
Top-down的DP基本上是個偷懶的方法，我們的建議如下：如果計算順序不難找，還是寫迴圈版，不要過分偷懶，因為遞迴還是有成本與限制，Python的遞迴深度預設是1000，即使有辦法更改，但在遞迴的深度還是會因為記憶體的限制而受限，因此在某些環境與系統之下(尤其架在視窗系統下)，遞迴的深度還是有一定的限制，超過限制會導致執行階段的錯誤。
在計算順序比較不好找或者比較麻煩時，而且系統是允許的狀況下，就採用top-down吧！最常見的情形就是Tree的DP，幾乎參加比賽的選手都寫遞迴的DFS版本，因為迴圈版的要找bottom-up順序(如P-3-1)，比較麻煩。不過這裡還是要建議：兩種都要會，可以偷懶的時候才偷懶。另外，Tree的DP與一維的DP，如果用Python解，通常都無法用top-down，因為遞迴會出問題。
註：Python在functools中有個功能lru_cache()可以自動幫函數做memoization，但本文件中還都是以自己寫memo的方式來做。
## 例題與習題
在本節中我們提出一些動態規劃的經典例題與習題，來讓大家更熟悉以DP的思維來設計演算法的方式，我們依照1D0D、2D0D、1D1D、以及2D1D與其他共分成四個小節，在下一節中我們在放了少數比較進階的例子。
### 1D0D
這一節我們先看一些1D0D的DP。事實上，在上一節的小朋友上樓梯的走法數就是之前出現過的費氏數列，也就是1D0D的一種最簡單形式。用陣列搭配迴圈或甚至使用Top-down的方法都可以很快的在$O(n)$求解。我們在第二章Q-2-5中曾經提出以矩陣快速冪來做到$O(\log n)$計算費氏數列的第$n$項，事實上就是這一類1D0D的優化方式，如果遞迴式改變時，相同的方法也都可以運用。
不過費氏數列那一類基本上沒有輸入資料的遞迴，其實根本存在數學解，而並非訓練演算法的好題目，大部分的題目是會搭配輸入資料的。我們之前用到過的前綴和(prefix-sum)其實也可以算是1D0D的DP，因為遞迴式是$ps[n]=ps[n-1]+a[n]$，其中資料放在$a[]$而$ps[n]$是前$n$項的和，另外像類似的prefix-minimum也都是類似的題目，這些都太簡單就不列在例題習題中了。第一個我們選的例題是前面用來說明的小朋友上樓梯，但是是有輸入資料的版本。
---
##### P-6-1. 小朋友上樓梯最小成本
小朋友玩上樓梯遊戲，每一步可以往上走一階或兩階，開始位置在第0階，從第一階開始每階都有一個數字，踩在第$i$階，分數就要扣第$i$階的數字，請問走到第$n$階的最少的扣分是多少。
Time limit: 1秒
輸入格式：第一行是正整數$n$。第二行有$n$個正整數，依序代表第1階開始的數字，數字間以空白隔開。$n \le 1e5$，每階的數字不超過1e4。
輸出：走到第$n$階的最小總扣分。
範例一輸入：
8
2 1 1 7 3 2 9 2
範例一輸出：
9
範例二輸入：
5
1 2 3 1 5
範例二輸出：
8
範例一說明：最小扣分是1+1+3+2+2=9。
範例二說明：最小扣分是2+1+5=8。
---
假設踩在第 $i$ 階的扣分是 $cost[i]$，而編號由0開始。基本的DP問題只要寫出遞迴關係就差不多完成了，通常子問題就是從小到大。根據這個原則定義$c[i]$是走到第 $i$ 階的最小扣分，因為最後一步一定是一階或兩階，我們很快可以得到：
$c[i] = cost[i] + min(c[i-1], c[i-2])$ for $c\ge 2$；初始條件呢？因為扣分沒有負的，我們很簡單可以知道$c[0]=cost[0]$且$c[1]=cost[1]$。
根據找到的遞迴關係，把$c[i]$存放在陣列中，計算的順序就是 $i$ 由小到大計算，程式如下很簡單，我們不另外開一個陣列$c[]$，直接將計算結果放在原來輸入的陣列。
```python=
n = int(input())
cost = [int(x) for x in input().split()]
for i in range(2,n):
cost[i] += min(cost[i-1],cost[i-2])
print(cost[n-1])
```
---
##### P-6-2. 不連續的表演酬勞
楊鐵心帶著義女穆念慈當街頭的武術表演者，他接到許多的邀約，每天均有一場。每一場表演都可以得到某些金額的報酬，但是武術表演很辛苦，無法連續兩天都進行表演，請你寫一支程式協助他決定應該接受那些表演以得到最大的報酬。
Time limit: 1秒
輸入格式：第一行是正整數 $n$。第二行有 $n$ 個非負整數，依序代表第1天開始每天邀約報酬，數字間以空白隔開。$n \le 1e5$，每天酬勞不超過10000。
輸出：最大可能獲得的總酬勞。
範例一輸入：
5
1 2 3 1 5
範例一輸出：
9
範例二輸入：
8
2 1 1 7 3 2 9 2
範例二輸出：
18
範例一說明：挑選1+3+5=9。
範例二說明：挑選2+7+9=18。
---
把每天可以獲得的酬勞放在一個一維陣列$p[]$中，再一次我們將子問題定義為：
$dp[i]$是前 $i$ 天可以獲得的最大報酬。
初始條件很容易想，$dp[0]=p[0]$，因為沒有選擇，$dp[1]$會是多少呢？因為兩天只能選擇其中之一，所以一定選大的，$dp[1]=\max(p[0],p[1])$。
要如何建構出遞迴關係式呢？我們可以這麼想：把第 $i$ 天選或不選分開考慮，
* 如果第 $i$ 天不選，前 $i$ 天的獲利就是前 $i-1$ 天的獲利，也就是$dp[i]=dp[i-1]$；
* 如果第 $i$ 天要選呢？我們可以獲得$p[i]$，但是第 $i -1$就不可選了，也就是前 $i-2$天的最大獲利，因此最大的獲利是 $p[i]+dp[i-2]$。
在第 $i$ 天選或不選之間挑最大的，我們得到：
$dp[i] = max(dp[i-1], p[i]+dp[i-2])$。
程式就很容易了，讓 $i$ 從小算到大就不需要遞迴了。
```python=
# p-6-2 max independent on array
n = int(input())
p = [int(x) for x in input().split()]
dp = [0]*n # max until i
dp[0] = p[0]
dp[1] = max(p[0], p[1])
for i in range(2,n):
dp[i] = max(dp[i-1], dp[i-2]+p[i])
print(dp[n-1])
```
下一題跟上一題看起來似乎有點類似。
---
##### P-6-3. 最小監控鄰居的成本
有一條長長的大街被劃分成 $n$ 個區段，編號依序為 1 ~ $n$。在第 $i$ 個區段設置監控設備的話，需要成本 $c[i]$，而可以監控第 $i -1$到第 $i +1$的區段(超出範圍可忽略)。現在要選一些區段裝設監控設備，以便每一個區段都可以被監控到，請計算最少的總成本。
Time limit: 1秒
輸入格式：第一行是正整數$n$。第二行有 $n$ 個非負整數，依序代表第 $i$ 個區段裝設監控設備的成本，數字間以空白隔開。$2 < n \le 1e5$，每處成本不超過1e4。
輸出：最小監控總成本。
範例一輸入：
5
1 2 3 1 5
範例一輸出：
2
範例二輸入：
8
2 1 1 7 3 2 9 2
範例二輸出：
6
範例一說明：挑選1+1=2。
範例二說明：挑選1+1+2+2=6。
---
在一維陣列$c[]$中有一群非負整數，我們要挑選總和盡量小，但是每個沒有被挑選的點必須左右至少有一點被挑到。看起來與前一題類似，假設我們以類似的方式定義$dp[i]$為前$i$個的最小成本，寫遞迴式的時候會碰到一點困難：如果$dp[i-1]$的值是有挑選到$i-1$的，那麼第 $i$ 個點已經被監控到，$dp[i]=dp[i-1]$；但是如果$dp[i-1]$的值來自沒有挑選到$i-1$，那麼第 $i$ 點變成非挑不可，但我們又不知道$i-1$是否已經有挑選。
改變一下子問題的定義，我們讓$dp[i]$是前 $i$ 個點的最小監控成本而且最後一點選在 $i$。那麼，成本$c[i]$需要加進來，前面的點雖然不確定那些點一定要挑，但是不可能第 $i -1$、$i-2$ 與 $i-3$ 都沒有挑選，否則 $i-2$就沒被監控了，因此得到：
$dp[i] = c[i] + min(dp[i-1], dp[i-2], dp[i-3])$ for $i>2$；
初始條件是$dp[0]=c[0]$，$dp[1]=c[1]$，$dp[2]=c[2]+\min(c[0],c[1])$，此處編號我們由0開始。而最後的解呢？不一定出現在$dp[n-1]$，因為也可能是$dp[n-2]$。程式如下，很簡單就不多做解釋。
```python=
# p-6-3 min dominating on array
n = int(input())
c = [int(x) for x in input().split()]
dp = [0]*n # min until i and last selected = i
dp[0] = c[0]
dp[1] = c[1]
dp[2] = c[2]+min(c[0], c[1])
# the last one must be at i-3, i-2, or i-1
for i in range(3,n):
dp[i] = c[i]+min(dp[i-3], dp[i-2],dp[i-1])
print(min(dp[n-1],dp[n-2]))
```
如果是剛開始接觸學習DP的人要留意，別人跟你說遞迴式很容易懂，但如果你自己碰到題目要列遞迴式的時候，往往列不出來或是列錯，所以在學習的過程不能只看別人怎麼解，而要了解思考的方式。
除了多看題目吸取經驗之外，碰到類似的狀況，通常的解決原則就是把子問題加條件，或是將子問題依照不同的條件再進一步分類。這一題你也可以思考將前 $i$ 個解分成兩類：$dp0[i]$代表第 $i$ 個沒選，$dp1[i]$ 代表第 $i$ 個有選，分類後會比較容易列式。但是這一題很多人會列錯遞迴式，原因是這題的成本並沒有單調性，並非範圍越大成本越高，$dp1[i]$ 可能會小於 $dp1[i-1]$。如何列式我們留給有興趣的人自己想一想，範例程式中有另外一支以這樣的方式設計的，如果你認真看一看，你會發現兩個程式做的事情是一樣的。我們要強調一下，達到解的思考方式每個人未必相同，有人覺得這樣想比較簡單，有人認為那樣做比較直覺，其實是要找到適合自己的思考模式。
下一題是個習題。
---
##### Q-6-4. 闖關二選一
某個遊戲要依序闖過 $n$ 個關卡，初始的時候有一個幸運數字，每個關卡有兩個關卡數字，你必須把自己的幸運數字調整為兩個關卡數字之一，才能通過此關卡，調整的成本是你的幸運數字與關卡數字的差值(絕對值)。請計算出最低闖關總成本。
舉例來說，一開始的幸運數字為1，$n=2$，第一關的過關數字為$(5, -5)$，第二關的過關數字為$(-3, -2)$。要依序通過兩關，假設第一關把幸運數字調整成 5，第二關調整為 -2，則需要成本為$|1–5|+|5–(-2)|=11$。如果，第一關把幸運數字 -5，第二關調整為 -3，則需要成本為$|1–(-5)|+|(-5)–(-3)|=8$。你可以看得出來，總共有四種方式過關，其中最小成本是 8。
Time limit: 1秒
輸入格式：第一行有兩個正整數 $n$ 與 $t$，代表關卡數以及初始幸運號碼。接下來有 $n$ 行，每行兩個整數，依序代表每一關的過關數字。$n\le 1e5$，過關數字的絕對值皆不超過1e4。
輸出：最小過關成本。
範例一輸入：
2 1
5 -5
-3 -2
範例一輸出：
8
範例二輸入：
3 0
-5 1
-8 3
-7 -7
範例二輸出：
9
---
Q-6-4提示：我們以狀態轉移的方式來思考，有 $n$ 個關卡要通過，每個關卡通過的成本跟上一關通過的方式有關，但是跟更早的無關。所以可以想成通過每一關有兩種狀態，達到第 $i$ 關的第 $j$ 種狀態的最低成本是$cost[i][j]$其中 $i\le n$ 而 $j=0$或$1$。列出相鄰兩關的成本計算方式即可。
下圖是一個例子。
---
##### Q-6-5. 二維最大子矩陣
輸入一個$m\times n$的二維整數矩陣$A$，要找一塊總和最大的連續子矩陣(也就是其中一塊矩形區域)，輸出其總和。以下圖為例，
| 2 | -2 | 3 | 3 |
| :--: | :--: | :--: | :--:|
| -6| 5 | 2 | -8 |
| 3| 7 |-2 | 4 |
挑選
| -2 | 3 |
| :--: | :--: |
| 5 | 2 |
| 7 |-2 |
可以獲得最大總和13。
Time limit: 4秒
輸入格式：第一行有兩個正整數 $m$ 與 $n$。接下來 $m$ 行每行 $n$ 個整數，代表矩陣由上而下由左而右的內容。$m$ 與 $n$ 皆不超過200，矩陣內的數字絕對值皆不超過1e4。
輸出：子矩陣的最大可能總和。
範例一輸入：
3 4
2 -2 3 3
-6 5 2 -8
3 7 -2 4
範例一輸出：
13
範例二輸入：
1 6
-2 1 3 -1 4 -5
範例二輸出：
7
---
這一個習題其實是之前的題目變化成二維的形式，給一個提示：想想看P-4-13。我們可以枚舉所有可能的$O(m^2)$個**列區間**，將每一個列區間，例如第 3 ~ 5 列，"黏"成一個一維陣列，然後求一維陣列的max subarray，這樣可以導致一個$O(m^2n)$時間複雜度的解。
### 2D0D
1D的DP，他們的子問題往往都是以一個整數由小到大編號，2D的DP的子問題通常是由一個二維陣列來編號，第一個要介紹的問題非常簡單，他其實是方格棋盤路徑數問題的有輸入資料版本。
---
##### P-6-6. 方格棋盤路線
在一個 $m\times n$ 方格棋盤上，每個格子都有一個分數(可正可負)，現在要從左上角的格子走到右下角，每次只能從當時位置移動到右方或下方的格子，請計算出經過路線上的數字的最大可能總和。以下圖為例，最大的總和路線是經過(2, -2, 5, 7, -5, 4)，總和為11。
| 2 | -2 | 3 | 3 |
| :--: | :--: | :--: | :--:|
| -6| 5 | 2 | -8 |
| 4 | 7 |-5 | 4 |
Time limit: 1秒
輸入格式：第一行有兩個正整數 $m$ 與 $n$。接下來 $m$ 行，每行 $n$ 個整數，代表方格由上而下，由左而右的內容。$m$ 與 $n$ 皆不超過200，矩陣內的數字絕對值皆不超過1e4。
輸出：最大總和。
範例一輸入：
3 4
2 -2 3 3
-6 5 2 -8
4 7 -5 4
範例一輸出：
11
範例二輸入：
2 5
1 2 3 1 -5
-2 5 -8 2 1
範例二輸出：
10
範例一說明：如題目中說明
範例二說明：先向右走三步，向下一步，再向右一步，得分1+2+3+1+2+1=10。
---
從第一節介紹的狀態轉移就知道，我們可以將到達每一個格子當作一種狀態，因為只能往右或往下移動，所以每一個格子的前置狀態就是他的左方與上方(如果有的話)。因此我們設計子問題的方式就是：以 $f[i][j]$ 當作是走到位置$(i,j)$所能獲得的最大得分，遞迴式為
$f[i][j] = \max(f[i-1][j], f[i][j-1]) + a[i][j]$；
其中 $a[i][j]$ 是該格子的分數。初始條件呢？因為最上面一列只能從左方走過來，而最左邊一行只能從上方走過來，所以我們可以對這兩個邊界單獨計算，另外一種方式是將超界的最左方與最上方訂為負的無窮大。計算的順序呢？根據原則，遞迴式等號右邊出現的必須在等號左邊出現的先計算，所以每一個格子的左方與上方只要先出現就是可以的順序，最直接的就是由上而下，由左至右。下面是範例程式，我們沒有另外宣告一個陣列放 $f[][]$，而是直接把它存在 $a[][]$ 中。時間複雜度很簡單$O( mn)$，因為有這麼多格子要算，每一格只要$O( 1)$。
```python=
# P-6-6 Grid max weight monotonic path O(mn)
m,n = [int(x) for x in input().split()]
a = []
for i in range(m):
a.append([int(x) for x in input().split()])
# first row and first column
for j in range(1,n):
a[0][j] += a[0][j-1]
for i in range(1,m):
a[i][0] += a[i-1][0];
# max of up and left
for i in range(1,m):
for j in range(1,n):
a[i][j] += max(a[i-1][j],a[i][j-1])
print(a[m-1][n-1])
```
**Longest Common Subsequence (LCS)** 是序列分析的重要問題，一個序列的子序列是指將其中某些元素刪除後所得到的序列，字串可以看成字母組成的序列，以”algorithm”為例，”algtm”與”lgh”都是它的子序列，但是”agl”則不是，因為你不可以調整位置重新排列。
輸入兩序列，LCS要找一個最長的序列，它是兩輸入序列的共同子序列。LCS可以是一種作為字串相似度的定義，有很多重要的應用。
---
##### P-6-7. LCS
輸入兩字串，計算其LCS的長度。
Time limit: 1秒
輸入格式：第一行與第二行個有一個字串，字串均只含小寫字母，長度不超過500。
輸出：LCS長度。
範例一輸入：
algorithm
alignment
範例一輸出：
4
範例二輸入：
fakefamefade
acefaaace
範例二輸出：
6
範例一說明：algm或algt都是LCS。
範例二說明：LCS是aefaae。
---
如果要暴力搜尋的話可慘了，一個長度 $n$ 的序列有 $2^n$ 個子序列，因為每一個位置都可以刪除或不刪除。假設第一個字串是 $s1$，第二個是 $s2$，以DP的思考我們來設法定義子問題。比對兩個字串最普通的方式是從前往後比對，我們定義 $lcs[i][j]$為：$s1$的前 $i$ 個字元與 $s2$ 的前 $j$ 個字元的LCS長度，也就是 $s1$ 與 $s2$ 的長度分別為 $i$ 與 $j$ 的prefix的LCS長度。
字串的字元編號由0開始，$s1$ 長度 $i$的最後一個字母是$s1[i-1]$，我們分兩個情形：
* 如果 $s1[i-1] \neq s2[j-1]$：既然兩者不相等，兩者中至少有一個對找LCS是沒有幫助的，也就是說，我可以刪掉 $s1$ 的最後一個字母 $s1[i]$ 或者刪掉 $s2[j]$，因為要找越長越好的，所以兩者取其大，
$lcs[i][j]=\max(lcs[i-1][j], lcs[i][j-1])$。
當然也可能兩者都刪除，因為是一直遞迴上去，兩者都刪的狀態是被包含在刪除其中一個的狀態之中。
* 如果 $s1[i-1]=s2[j-1]$：因為我們只計算LCS的長度，跟在哪個位置對中無關，所以既然對中，不對白不對，把其中一個刪除不會更好，因此可以得到
$lcs[i][j]=lcs[i-1][j-1]+1$。
我們已經完成遞迴式的設計了，邊界條件(初始條件)呢？依照我們定義，$lcs[i][0]$ 與 $lcs[0][j]$ 代表其中一個字串的長度為0的狀況，長度為0字串與他人的LCS當然是空字串，所以$lcs[i][0]=lcs[0][j]=0$。整理一下結果：
$$
lcs[i][j] = \left\{
\begin{array}{ll}
0 & \text{if } i=0 \text{ or } j=0 \\
lcs[i-1][j-1]+1 & \text{if } s1[i]=s2[j]\\
\max(lcs[i-1][j],lcs[i][j-1]) & \text{otherwise}
\end{array}
\right.
$$
是不是有點眼熟呢？把 $lcs[][]$ 看成一個表格，每一個格子跟左方、上方與左上方的格子有關，當然還要看 $s1[i]$ 與 $s2[j]$ 是否相等。跟前一題一樣的計算順序就可以滿足DP避免遞迴的要求，所以由上而下，由左至右就是一個好的順序。
以下是範例程式，時間複雜度是$O( mn)$，因為每格只需要$O( 1)$。請留意$lcs[i][j]$的index與字串字元的index編號差1，因為 $s1$ 長度 $i$的最後一個字元是$s1[i-1]$。
```python=
# P-6-7 LCS O(mn)
s1 = input()
s2 = input()
m,n = len(s1),len(s2)
# initial dp table
lcs = [[0]*(n+1) for i in range(m+1)]
for i in range(1,m+1):
for j in range(1,n+1):
if s1[i-1] == s2[j-1]:
lcs[i][j] = lcs[i-1][j-1]+1
else:
lcs[i][j] = max(lcs[i-1][j],lcs[i][j-1])
print(lcs[m][n])
```
其實很多DP的程式都很簡單，遞迴式找出來之後，迴圈與表格從小到大拉過去就結束了。這一題我們多講一個空間上的問題，二維的問題有的時候會有空間用量太大的麻煩。
如果兩個字串長度到1萬，時間或許還可以接受，但是空間會出現不足的問題。如果真的需要這麼大的表格，那也是無可奈何，但如果只是要算LCS長度，根據上面的遞迴式，我們事實上並不需要一直留著整張表格。此外，Python的二維陣列(list of list)存取時間也較慢。
計算 $lcs[i][j]$ 時，我們只需要第 $i$ 列與前一列就足夠了，所以有一個直接節省記憶體的方法：使用兩個一維陣列 $p$ 與 $d$，永遠把 $p$ 當作前一列，$d$當作目前的列。每次迴圈進入時，從$p$算到$d$，在迴圈尾將兩者交換。
```python=
p,d = [0]*n, [0]*n # initial
for i in range(m):
# compute from p to d
p,d = d,p # swap two row, O(1)
# the answer (last row) is in p
```
要留意下方的寫法是錯誤的，因為 $p = d$ 這個指令會導致兩者是同一個物件，除非你改成 $p = d[:]$，但這會多了複製的時間。
```python=
# WRONG way
p,d = [0]*n, [0]*n # initial
for i in range(m):
# compute from p to d
p = d # assign d to p, O(1)
# but now p and d pointing to the same one
```
這個方法有時稱為**滾動陣列**。以下是LCS的範例程式。
```python=
# P-6-7 LCS O(mn)
s1 = input()
s2 = input()
m,n = len(s1),len(s2)
# initial dp table
p,d = [0]*(n+1), [0]*(n+1)
for i in range(1,m+1): # m times
# p is prev row, d is current row, from p to d
for j in range(1,n+1):
if s1[i-1] == s2[j-1]:
d[j] = p[j-1]+1
else:
d[j] = max(p[j],d[j-1])
p,d = d,p # swap
#
print(p[n])
```
**End of Chapter 6 (I)**
續接 [AP325-Python 第6章 動態規劃 (II)](/7CGWqR4tQ2Oc99l26Akmqw)
Sign in with Wallet
Connect another wallet