# 前言
動態規劃這個單元是我認為最為困難的單元，因為題目變化的多樣性，跟程式的複雜讓我學起來特別吃力。這一章我會一步步來講解這個單元的奧妙之處。
# 動態規劃是什麼
「是動態？還是規劃？」—— 他既非動態也非規劃。動態規劃是一個透過小的子問題解決大問題的技巧，很像分治（1-7）：大事化小，小事化無。
那為什麼叫動態規劃？發明動態規劃的人是 Bellman，他在自傳《Eye of the Hurricane: An Autobiography》裡提到過名字由來（有興趣可以自行查找），但這裡先不劇透 —— 重點是它的核心概念可以用一句話總結：
長江後浪推前浪，一替新人換舊人。
這句話呼應了動態規劃最核心的想法：用以前的資訊來幫助我們得到當前最新的資訊。
# 從費氏數列出發
f(n) = f(n-1) + f(n-2) ， f(0) = 0 ， f(1) = 1 。可以把動態規劃想像成是一個公式，只要我們把公式需要的資訊先取得了，就可以慢慢往後推得後面的資訊。有了 f (0)、f (1) 之後，就可以依序算出 f (2), f (3) … f (n)，求出 f (n) 的時間複雜度為 O(n) 。
這樣子從底層往上慢慢推出後面資訊的方式稱為 Bottom-Up，與 Bottom-Up 相反的方式稱為 Top-Down。
Top-Down 是直接用遞迴求 f (n)：
// [來源：CISCON 2023] | |
int f(int n) | |
{ | |
if( n == 0 ) return 0; | |
if( n == 1 ) return 1; | |
return f(n-1) + f(n-2); | |
} |
這樣子的時間複雜度是 O(n) 嗎？我們畫出遞迴樹來看看：
Fib(5)
/ \
Fib(4) Fib(3)
/ \ / \
Fib(3) Fib(2) Fib(2) F(1)=1
/ \ / \ / \
Fib(2) F(1)=1 F(1)=1 F(0)=0 F(1)=1 F(0)=0
/ \
F(1)=1 F(0)=0
你會發現有地方我們重複計算了，先前已經求過 f (2) 與 f (3) 了。因此如果我們把之前算過的存起來，如果某次突然要使用到之前算過的資訊就可以直接拿出來用了，這就是動態規劃 Top-Down 的精神。
// [來源：CISCON 2023] | |
int dp[101]; | |
int f(int n) | |
{ | |
if( n == 0 ) return 0; | |
if( n == 1 ) return 1; | |
if( dp[n] != 0 ) return dp[n]; // 算過了，直接拿之前算出來的東西 | |
else | |
{ | |
dp[n] = f(n-1) + f(n-2); | |
return dp[n]; | |
} | |
} |
因為這樣子我們可以保證這 n 個東西我們只會算過 1 次，時間複雜度又變回乾淨的 O(n) 了。這個「把算過的存起來」的技巧叫做 memoization（記憶化），是 Top-Down DP 的核心。
# Top-Down vs Bottom-Up
| 缺點 | 優點 | |
|---|---|---|
| Top-Down | 時間複雜度常數大（pass by value & pass by reference 的取捨、遞迴太深會導致 stack overflow） | 轉移式很直覺，只要記得把算過的存起來就好 |
| Bottom-Up | 轉移式比較不直覺 | 寫起來很乾淨，時間複雜度常數小 |
Bottom-Up 是動態規劃最常見的使用方法，Top-Down 一個不小心遞迴太深就出大事了（見 1-2 遞迴 提過的呼叫堆疊成本）。兩種寫法基本上是可以互換的，可是通常題目中使用其中一種方法會比較好寫，而該使用甚麼方法比較方便程式碼看起來比較簡潔就看題目了。
這個單元要學好就要學會怎麼列出轉移式，而甚麼是轉移式等等看例題會解釋，簡單的題目沒列出來轉移式可能影響不大，可是比較複雜的題目列出來慢慢推出正確的轉移式會對寫程式的方向有很大的影響。
# DP 的分類：從狀態維度理解
CISCON 課程用一個很實用的方式分類 DP 題目：看轉移式需要幾個維度的狀態。這個分類法能幫助你快速判斷一題大概要開幾維的 dp 陣列。
- 1D0D：狀態只跟一個變數有關，例如
dp[i]= 前 i 個的答案 - 2D0D：狀態跟兩個獨立變數有關，例如
dp[i][j]= 前 i 個物品、容量 j 的答案（背包問題） - 1D1D：狀態跟一個位置 + 一個額外維度有關，例如
dp[i][k]= 第 i 天做第 k 件事的答案 - 2D1D 與其他：座標型 DP（例如二維矩陣路徑）疊加額外限制
這個分類法不是嚴格的數學定義，而是幫助你在看到新題目時，先問自己：「我需要幾個變數才能唯一確定一個子問題？」 這個問題的答案，通常就是你要開的陣列維度。
# 排列組合類 DP：骰子與硬幣湊數
# CSES Dice Combinations
骰子有 1~6 點，現在可以骰無限顆骰子，依序骰每一個骰子，求最後共有幾種骰法會使所有骰子的點數和為 n。例如 n=3，answer=4： 1+1+1 、 2+1 、 1+2 、 3 。
動態規劃的第一個步驟都是定義轉移式，有點類似定義一個 Function 的概念。像是這題我們會定義 dp[i] = 骰出點數為 i 的組合數。
對於點數 i 來說，要使骰出的點數總和為 i，會有 6 種可能：點數 i-6 時再骰出 1 個 6 點、點數 i-5 時再骰出 1 個 5 點、點數 i-4 時再骰出 1 個 4 點…… 以此類推。因此轉移式為：
dp[i] = dp[i-1] + dp[i-2] + ... + dp[i-6] （加法原理）
如此一來，很簡單的就可以用迴圈解決了，時間複雜度 O(n) 。題目有說答案可能很大，只要輸出 mod 10^9 + 7 的結果就好。
// [來源：CISCON 2023] | |
const int mod = 1e9 + 7; | |
signed main(void) | |
{ | |
int n; | |
cin >> n; | |
dp[0] = 1; | |
for(int i=1;i<=n;i++) | |
{ | |
for(int k=1;k<=6;k++) | |
{ | |
if( i - k >= 0 ) dp[i] += dp[i-k], dp[i] %= mod; | |
} | |
} | |
cout << dp[n] << "\n"; | |
return 0; | |
} |
# CSES Coin Combinations I
有 n 種硬幣，每種硬幣的面額分別是 c_i ，接下來每一次你可以選擇其中一種硬幣（可以重複拿一樣的），求最後湊出總金額 x 的選法有幾種。
定義轉移式： dp[i] = 湊出總和為 i 的湊法有幾種。對於總和 i 來說，你有可能是透過 i-c1 再拿 1 個 c1 硬幣得來的、 i-c2 再拿 1 個 c2 硬幣得來的…… 因此你會發現轉移式跟骰子那一題一樣，差別只在於骰子固定 1~6，硬幣是 c1~cn。
對於每一個總和 i 我們都需要去枚舉 c1~cn，因此整體時間複雜度為 O(nx) 。
// [來源：CISCON 2023] | |
int n,m; | |
cin >> n >> m; | |
vector<int> a(n); | |
for(int i=0;i<n;i++) | |
{ | |
cin >> a[i]; | |
} | |
dp[0] = 1; | |
for(int i=1;i<=m;i++) | |
{ | |
for(int k=0;k<n;k++) | |
{ | |
if( i - a[k] >= 0 ) | |
{ | |
dp[i] += dp[i-a[k]]; | |
dp[i] %= mod; | |
} | |
} | |
} | |
cout << dp[m] << "\n"; |
# 選擇困難的動態規劃：1D1D
# AtCoder DP Contest Frog 1
現在有一隻青蛙在第一個石頭，n 個石頭，每一個石頭的高度數字 h_i 。這一隻青蛙每一次只能跳 1 格或 2 格。如果原本在高度 a 的石頭，跳到高度 b 的石頭需要花費 |a-b| 。求青蛙最後跳到第 n 個石頭所需要的最少花費。
對於青蛙第 i 個石頭來說只有兩種可能：從第 i-1 個石頭跳過來、從第 i-2 個石頭跳過來。所以如果我們能算出跳到 i-1 與 i-2 的最佳答案，就可以求得跳到 i 的最佳答案。
定義 dp[i] = 跳到 i 所需要的最小花費。 dp[1] = 0 ， dp[2] = |h1 - h2| 。如果第 i-2 個石頭的高度是 a，第 i-1 個石頭的高度是 b，從第 i-2 個石頭跳過來所需花費為 dp[i-2] + |a - h_i| ，從第 i-1 個石頭跳過來所需花費為 dp[i-1] + |b - h_i| 。要選出最好的方案，因此整個轉移式合併在一起就會變成：
dp[i] = min( dp[i-2] + |a - h_i| , dp[i-1] + |b - h_i| )
整體時間複雜度 O(n) 。
// [來源：CISCON 2023] | |
vector<int>a(n+1),dp(n+1,(int)1e9); | |
for(int i=1;i<=n;i++) cin >> a[i]; | |
dp[1] = 0 , dp[2] = abs(a[2]-a[1]); | |
for(int i=3;i<=n;i++) | |
{ | |
dp[i] = min( dp[i-1] + abs(a[i]-a[i-1]) , dp[i-2] + abs(a[i]-a[i-2]) ); | |
} | |
cout << dp[n] << "\n"; |
# 闖關二選一（AP325）
某個遊戲要依序闖過 n 個關卡，初始的時候有一個幸運數字，每個關卡有兩個關卡數字，你必須把自己的幸運數字調整為兩個關卡數字之一，才能通過此卡，調整的成本是你的幸運數字與關卡數字的差值 (絕對值)。請計算出最低闖關總成本。
舉例來說，一開始的幸運數字為 1，n=2，第一關的過關數字為 (5, -5)，第二關的過關數字為 (-3, -2)。要依序通過兩關，假設第一關把幸運數字調整成 5，第二關調整為 - 2，則需要成本為 |1-5|+|5-(-2)|=11 。如果，第一關把幸運數字 - 5，第二關調整為 - 3，則需要成本為 |1-(-5)|+|(-5)-(-3)|=8 。你可以看得出來，總共有四種方式過關，其中最小成本是 8。
| 範例輸入 #1 | 範例輸出 #1 |
|---|---|
| 2 1 5 -5 -3 -2 |
8 |
這是跟青蛙跳石頭同類型的 1D1D DP：每一關都有兩種選擇（選數字 0 或選數字 1），我習慣在寫動態規劃的題目時默念一個口訣，「選與不選」，選了這個要做甚麼，不選這個要做甚麼。
dp[i][0] 代表第 i 關選擇第一個數字時的最小成本， dp[i][1] 代表選擇第二個數字時的最小成本：
dp[i][0] = min( |number[0]-number[2]| + dp[i-1][0], |number[0]-number[3]| + dp[i-1][1] )
這一行是代表選擇 number[0] 這個數字然後看看選擇上兩個數字有甚麼差別然後取最小值。因為 dp 陣列只會需要上個狀態所以可以節省點記憶體：
#include<bits/stdc++.h> | |
using namespace std; | |
int main(){ | |
int n,t,number[4]; | |
int dp[2]={0}; | |
cin>>n>>t; | |
for(int i=0;i<4;i++) number[i]=t; | |
for(int i=0,buffer;i<n;i++){ | |
cin>>number[0]>>number[1]; | |
buffer=dp[0];// 因為等等會修改到 dp [0] 的值所以要先保留起來 | |
dp[0]=min(abs(number[0]-number[2])+dp[0],abs(number[0]-number[3])+dp[1]); | |
dp[1]=min(abs(number[1]-number[2])+buffer,abs(number[1]-number[3])+dp[1]); | |
number[2]=number[0]; | |
number[3]=number[1]; | |
} | |
cout<<min(dp[0],dp[1]); | |
} |
# 方格棋盤路線（AP325，座標型 DP）
在一個 m×n 方格棋盤上，每個格子都有一個分數 (可正可負)，現在要從左上角的格子走到右下角，每次只能從當時位置移動到右方或下方的格子，請計算出經過路線上的數字的最大可能總和。
| 範例輸入 #1 | 範例輸出 #1 |
|---|---|
| 3 4 2 -2 3 3 -6 5 2 -8 3 7 -5 4 |
11 |
這一題在 AP325 講義裡示範了 button-up 的寫法，我則用了 top-down 的寫法來試試看，這題的前置狀態有兩個所以跟上兩題的感覺不太一樣，時間複雜度也不一樣是 O(mn) 。轉移式：
f[i][j] = max(f[i-1][j], f[i][j-1]) + a[i][j]
這裡的 a[i][j] 是格子裡的分數， f[i][j] 的定義就是走到位置 (i,j) 所能獲得的最大得分。
#include <bits/stdc++.h> | |
using namespace std; | |
#define N 205 | |
#define INF -100004 | |
int dp[N][N],m,n,a[N][N]; | |
int f(int _m,int _n){ | |
if(_m > m || _n > n || _m < 1 || _n < 1) return INF; | |
if(_m == 1 && _n== 1) return a[1][1]; | |
if(dp[_m][_n]!=0) return dp[_m][_n]; | |
return dp[_m][_n]=max(f(_m-1,_n),f(_m,_n-1))+a[_m][_n]; | |
} | |
int main(){ | |
cin>>m>>n; | |
for(int i=1;i<=m;i++){ | |
for(int j=1;j<=n;j++){ | |
cin>>a[i][j]; | |
} | |
} | |
cout<<f(m,n); | |
} |
if(_m > m || _n > n || _m < 1 || _n < 1) return INF; 這裡要記得不可以寫 return 0 因為數值有可能是負的所以要用負的無窮大，而無窮大要設多少就是看題目限制，我這次 dp 用 int 宣告如果題目的數字很大就必須要改成 long long。
if(dp[_m][_n]!=0) return dp[_m][_n]; 如果 dp[_m][_n] 已經被計算過就直接回傳，不需要重複計算。
if(_m == 1 && _n== 1) return a[1][1]; 這一行是終止條件，可能會想說為甚麼不易開始直接 dp[1][1]=a[1][1] 就好了，這樣就不用每次遞迴都判斷一次，因為如果 a [1][1] 是 0 的話就會繼續遞迴下去，繼續往下遞迴馬上就會碰到終止條件兩邊都會回傳 INF (infinite) 然後取最大值一樣是 INF 這樣程式就出 bug。
# LCS（Longest Common Subsequence）：兩個序列的 DP
講這一題前先來提到動態規劃的經典題 LCS（Longest Common Subsequence）中文叫做最長共同子序列。在 LCS 問題中，給定兩個序列（通常是字串），我們的目標是找到它們之間最長的共同子序列，該子序列不要求連續，只需要保持原始序列中的相對順序。
我們可以建立一個二維的狀態表格，其中行和列分別代表兩個序列的元素，表格的每個格子記錄了到目前為止的最長共同子序列的長度。填充表格的規則如下：
- 如果兩個序列的某個元素相等，則該格子的數值等於左上角格子的數值加 1
- 如果兩個序列的某個元素不相等，則該格子的數值等於左方格子和上方格子中的較大值
填充完整個表格後，右下角格子的數值就是最長共同子序列的長度。
// 這裡附上 LCS 問題的 top-down 函式寫法 | |
int f(int i,int j){//m 代表 s1 的長度，n 代表 s2 的長度 | |
if(i < 1 || j<1 || i>m || j>n) return 0;// 邊界 | |
if(dp[i][j]>0) return dp[i][j];// 計算過的直接回傳 | |
if(s1[i]==s2[j]) | |
return dp[i][j]=f(i-1,j-1)+1; | |
else | |
return dp[i][j]=max(f(i-1,j),f(i,j-1)); | |
} |
# Local alignment: LCS 應用題（APCS）
輸入兩字串，計算 local alignment 的最大分數。評分機制為：兩字母相同得 8 分，相異 - 5 分，字母與空白對應 - 3 分。
輸入格式：第一行與第二行各有一個字串，字串均只由 ATCG 四個字母組成，長度不超過 500。
| 範例輸入 #1 | 範例輸出 #1 |
|---|---|
| ATATCTTAACTGG CGCGGATCATAA |
43 |
範例一說明：第一個字串取 ATCTTAA，第二個取 ATCATAA。
講解一下這一題的程式碼，根據題目如果相同的話就 + 8 分相異 - 5 分字母與空白對應就 - 3 分，所以按照 LCS 的想法來思考在稍微變化一下 dp[i][j] 的定義就是在 a 的第 i 個字元跟 b 的第 j 個字元為結尾的狀況下的最大分數，知道 LCS 定義再來稍微去變化一下。可以發現轉移式跟 LCS 非常像：
dp[i][j] = dp[i-1][j-1]+5 | a[i-1]=a[j-1]
dp[i][j] = max(dp[i-1][j]-3, dp[i][j-1]-3, dp[i-1][j-1]-5) | a[i-1]!=a[j-1]
我們先來看看這個例子：
C___TTAACT
CGGATCA__T
我們來觀察甚麼叫做與空白對應，首先第一個字母都是 C 沒問題，在來判斷第二個字母的時候，如果先不看空白格就是 T 對上 G 很明顯這兩個字母不一樣，接下來有四種可能：
- 兩個字母都選也就是原本的 8 分然後 - 5 分，字串就是 CT 對上 CG
- 選擇 T 然後然後不選 G 這裡的不選不是丟棄的意思而是先給它對應到空白如果用 i 跟 j 來代表 a 的前 i 個字元跟 b 的前 j 個字元那就是現在
dp[i][j]=dp[i][j-1]用數字來看就是dp[2][2]=dp[2][1]，字串就是 CT 對上 C_ - 跟上述的步驟幾乎一樣只是方向不一樣而已字串是 C_ 對上 CG
- 最後還有一種就是不管選了哪種分數都會是負的那就乾脆放棄前面從現在開始重新選，
if(dp[i][j]<0) dp[i][j]=0;這就是這行代表的意思
#include<bits/stdc++.h> | |
using namespace std; | |
#define N 505 | |
int main(){ | |
int dp[N][N]={0},mx=0; | |
string a,b; | |
cin>>a>>b; | |
for(int i=1;i<=(int)a.size();i++){ | |
for(int j=1;j<=(int)b.size();j++){ | |
if(a[i-1]==b[j-1]) | |
dp[i][j]=dp[i-1][j-1]+8; | |
else | |
dp[i][j]=max(dp[i-1][j]-3, | |
max(dp[i-1][j-1]-3,dp[i-1][j-1]-5)); | |
if(dp[i][j]<0) dp[i][j]=0; | |
mx=max(mx,dp[i][j]); | |
} | |
} | |
cout<<mx; | |
} |
有時候選擇上或是左分數都一樣那就代表都可以，我這邊統一優先表示上。灰色的部分代表原本數值是負的。
答案不一定都出現在最後面 —— 這跟一般 LCS 的差別在於這題允許「放棄前面重新開始」，所以要在每個格子填完之後就更新全域最大值 mx ，而不是只看右下角。
# 0/1 背包問題：DP 中最經典的問題
# AP325 的版本：大賣場免費大搬家
你抽中了大賣場的周年慶的抽獎活動，在不超過總重量 W 的限制下，你可任意挑選商品免費帶走。現場一共 n 項商品，每項商品有它的重量與價值，每項商品只可以選或不選，不可以拆開只拿一部份。請計算可以獲得的最大價值總和。
輸入格式：第一行有兩個正整數 n 與 W。第二行 n 個正整數，依序代表商品的重量，第三行有 n 個正整數，依序代表對應 n 項商品的價值。同一行數字間以空白隔開。n ≤ 100，W 與各商品重量及價值皆不超過 1e5。
| 範例一輸入 | 範例一輸出 |
|---|---|
| 7 10 3 4 2 3 3 6 5 5 5 2 4 4 5 6 |
14 |
# CISCON 課程：系統化推導 0/1 背包
0/1 背包問題是動態規劃當中最具代表性的問題之一，目前屬於 NP-Hard（還沒有找到多項式時間內的解法）。題目會給 n 個物品，容量 m 的背包，第 i 個物品會佔據背包 wi 的容量，價值為 vi ，你的目標是最後讓背包裡的所有物品價值越高越好。
定義 dp[i][k] 表示考慮前 i 個物品的情況下，背包容量為 k 時所能得到的最大價值。對於 dp[i][k] 來說，只有兩種選擇：拿第 i 個物品、不拿第 i 個物品。
如果我們要拿第 i 個物品，且當前背包只有 k 的容量，那在我們考慮前 i-1 個物品時，背包容量只能有 k-wi （因為拿第 i 個物品會佔據掉 wi 的容量，如果在考慮前 i-1 個物品時就用掉了超出 k-wi 的容量，第 i 個物品是裝不下容量只有 k 的背包的）。因此如果我們要拿第 i 個物品，轉移式為： dp[i][k] = dp[i-1][k-wi] + vi
如果我們不拿第 i 個物品，且當前背包只有 k 的容量，轉移式很簡單： dp[i][k] = dp[i-1][k]
把這兩種可能的轉移式合併在一起就會變成：
dp[i][k] = max( dp[i-1][k] , dp[i-1][k-wi] + vi )
而我們最後要求的答案是 dp[n][m] （n 個物品、背包容量 m）。因此我們就必須依序求出 dp[1][0~m] , dp[2][0~m] , … dp[n][0~m] 。求出 dp[i][0~m] 之前必須先把 dp[i-1][0~m] 求得，而我們已知 dp[0][0~m] 的結果都是 0。因此我們可以從底部開始推答案，推出 dp[n][m] 的結果，這就是動態規劃最重要的核心精神。整體時間複雜度： O(nm) 。
// [來源：CISCON 2023] | |
for(int i=1;i<=n;i++) | |
{ | |
for(int k=0;k<=m;k++) | |
{ | |
if( k - w[i] >= 0 ) dp[i][k] = max( dp[i-1][k] , dp[i-1][ k - w[i] ] + v[i] ); | |
else dp[i][k] = dp[i-1][k]; | |
} | |
} | |
cout << dp[n][m] << "\n"; |
# 我原本的一維寫法
這裡我示範只用一維陣列的寫法，我還蠻喜歡這個寫法：
#include <bits/stdc++.h> | |
using namespace std; | |
#define N 105 | |
int main(){ | |
pair<int,int> pii[N];//first wide,second price | |
int n,w; | |
cin>>n>>w; | |
for(int i=0;i<n;i++) | |
cin>>pii[i].first; | |
for(int i=0;i<n;i++) | |
cin>>pii[i].second; | |
int dp[w+2]={0}; | |
for(int i=1;i<=n;i++){ | |
for(int j=w;j>=pii[i-1].first;j--){ | |
dp[j]=max(dp[j], | |
dp[j-pii[i-1].first]+pii[i-1].second); | |
} | |
} | |
cout<<dp[w]; | |
} |
for(int j=w;j>=pii[i-1].first;j--) 來講講這一行的迴圈，我們現在要嘗試放入 pii[i-1] 這個物品，如果現在 j 比我們要放入的物品的重量還小那很顯然就是放不進去就直接等於之前的最佳解，不會有更新到答案的可能，然後如果放得進去那就要判斷了，然後為什麼這個迴圈要倒著跑？
正著跑不行嗎？不行！ 因為題目規定一個物品只能選或不選，你不能選兩個三個或四個，你只能選一個，所以要從後面跑回來，這樣才不會重複選到了。 dp[j]=max(dp[j],dp[j-pii[i-1].first]+pii[i-1].second); 這裡的意思就是不選或選，不選就是直接不更新答案跟之前 dp[j] 的最佳解一樣，選的話就是要更新，判斷選或不選只是兩個比較看哪種得到的利益比較多就選哪個。
# DP 優化：滾動陣列
背包問題的瓶頸：時間複雜度我們可能無法改變，目前找不到什麼好方法。那我們來看看空間複雜度。
需要開 n×m 的 dp 表格去紀錄（除了無限背包有 O(m) 的作法），因此空間複雜度為 O(nm) 。DP 是一個用空間換取時間的技巧，也就是說 n×m 如果太大，我們是完成不了 0/1 背包問題的。但其實 0/1 背包問題也有空間複雜度 O(m) 的作法，所以接下來我們來講 DP 當中的第一個優化技巧滾動陣列。
如果一般的動態規劃是：「長江後浪推前浪，一替新人換舊人」，那麼被滾動陣列優化後的動態規劃就是：「長江後浪推前浪，前浪死在沙灘上」。
不是把陣列拿起來滾，滾動陣列的核心精神是：把沒有用到的陣列拿來繼續重複使用。其實就是有點資源回收的概念。
我們來看看 0/1 背包問題： dp[i][k] = max( dp[i-1][k] , dp[i-1][k-wi] + vi ) 。有發現什麼事情嗎？如果我們現在正在算 dp[5][0~m] ，那麼 dp[1][0~m] , dp[2][0~m] , dp[3][0~m] 以後都用不到了，因為每一次轉移都只要知道前一次的結果，這個時候滾動陣列這個技巧就可以派上用場了。
對於背包問題來說只需要記錄前 1 次的結果，我們就可以開兩組長度為 m 的陣列就好，其中一組紀錄上一次的結果，其中一組紀錄這一次轉移的結果，這樣的話空間複雜度就從 O(nm) 被我們優化成 O(m) 。
我自己習慣把陣列開成 dp[2][m] ，然後假設 i 是奇數時就表示 i-1 是偶數，因此可以寫成：
dp[i mod 2][k] = max( dp[(i-1) mod 2][k], dp[(i-1) mod 2][k-wi] + vi )
// [來源：CISCON 2023] | |
for(int i=1;i<=n;i++) | |
{ | |
for(int k=0;k<=m;k++) | |
{ | |
if( k - w[i] >= 0 ) dp[i][k] = max( dp[(i-1)%2][k] , dp[(i-1)%2][ k - w[i] ] + v[i] ); | |
else dp[i][k] = dp[(i-1)%2][k]; | |
} | |
} | |
cout << dp[n%2][m] << "\n"; |
# 0/1 背包甚至可以不使用二維陣列
因為每一次都是拿前 1 次的結果，而且結果是可以一直使用的不用清空，所以其實 0/1 背包問題可以只開一維陣列解決。但是有個超級大的陷阱。
如果我們寫成這樣會發生什麼事情？假設 dp[10] 我們拿了第 1 個物品，這個物品的容量是 10，那如果我在轉移 dp[20] 的時候： dp[20] = dp[20-10] + v_1 ，我們重複拿了第 1 個物品 2 次！這是不合法的！
// [來源：CISCON 2023] | |
// 錯誤示範：正著跑會重複選取同一個物品 | |
for(int i=1;i<=n;i++) | |
{ | |
for(int k=0;k<=m;k++) | |
{ | |
if( k - w[i] >= 0 ) dp[k] = max(dp[k],dp[k-w[i]]+v[i]); | |
} | |
} |
但是如果我們如果把第二個迴圈倒著回來？我們每一次拿的資訊都是前一次的資訊，不會重複拿，這樣就完成一維陣列版本的 0/1 背包了：
// [來源：CISCON 2023] | |
for(int i=1;i<=n;i++) | |
{ | |
for(int k=m;k>=w[i];k--) | |
{ | |
dp[k] = max(dp[k],dp[k-w[i]]+v[i]); | |
} | |
} |
這正是我原本一維寫法背後的原理 —— 這一段跟前面「大賣場免費大搬家」我一維寫法的迴圈是同一招，現在你知道為什麼要倒著跑了。
那這個正著跑的版本是什麼背包？ 我們剛剛說這樣子因為會重複拿同一個物品，不符合 0/1 背包。那什麼樣的背包問題可以重複拿同一個物品？無限背包！ 因此無限背包也可以這樣寫。
# 無限背包問題
跟 0/1 背包問題要求的東西一樣，只是每一個物品的數量是無限的。由於物品可以重複拿，我們的狀態就不用特別註明當前是考慮前幾種物品，因此我們重新定義轉移式： dp[i] = 背包容量為 i 時，所可以得到的最大價值。
對於容量 i 來說有 m 種可能：在最大容量 i-w1 時再拿一個第 1 種物品、在最大容量 i-w2 時再拿一個第 2 種物品…… 你有發現嗎？是不是跟前面骰子還有硬幣那一題一樣了！只差在最後要求的東西不一樣而已。
對於容量 i 來說拿第 k 個物品的話： dp[i] = max( dp[i], dp[i-w_k] + v_k ) ，整體時間複雜度： O(nm) 。
// [來源：CISCON 2023] | |
for(int i=1;i<=m;i++) | |
{ | |
for(int k=1;k<=n;k++) | |
{ | |
dp[i] = max(dp[i],dp[i-w[i]]+v[i]); | |
} | |
} | |
cout << dp[m] << "\n"; |
# 置物櫃出租（APCS，無限背包的簡化版）
王老先生有一個置物櫃，共有 M 個相同大小的格子，置物櫃目前已經租給 n 個客戶，第 i 位客戶所租的大小為 f (i) 個格子。目前王老先生自己需要使用 S 個格子的置物櫃，如果剩下的容量不夠，就必須退掉某些客戶的租約。假設每個客戶所租容量只能全退或全不退，而退租第 i 個客戶損失的利益與其所租容量 f (i) 相同，請寫一支程式計算王老先生最小的損失利益。
| 範例一輸入 | 範例一輸出 |
|---|---|
| 3 10 6 4 4 1 |
5 |
這題的重點交給你們自己抓好了，我直接來換句話說：
- M (總格子數)-S (王老先生自己需要使用格子)= 能租給客人的格子數
- 分配這些能租給客人的格子
- 原本的利益 - 剩下的格子最佳分配利益 = 最小損失利益
因為這題的每個格子的價值都是 1 所以就會顯得比較簡單，這其實是一個每個物品只能選一次、但每個物品的「重量」跟「價值」相等的 0/1 背包（不是無限背包，因為每位客戶只能整組退或不退，不能重複退同一位客戶）。
#include<bits/stdc++.h> | |
using namespace std; | |
#define N 101 | |
#define W 200005 | |
int dp[W]={0}; | |
int main(){ | |
int n,m,s,a[N],all=0; | |
cin>>n>>m>>s; | |
for(int i=0;i<n;i++){ | |
cin>>a[i]; | |
all+=a[i]; | |
} | |
m-=s; | |
for(int i=1;i<n;i++){ | |
for(int j=m;j>=a[i-1];j--) | |
dp[j]=max(dp[j],dp[j-a[i-1]]+a[i-1]); | |
} | |
cout<<all-dp[m]; | |
} |
# d253. 00674 - Coin Change（多重背包的變形，可以重複選）
給你一個金額（n cents），請你回答共有多少種硬幣組合的方式。例如：n=11，那麼你可以有以下 4 種硬幣的組合：
1 個 10 cent 的硬幣加上 1 個 1 cent 的硬幣
2 個 5 cent 的硬幣加上 1 個 1 cent 的硬幣
1 個 5 cent 的硬幣加上 6 個 1 cent 的硬幣
11 個 1 cent 的硬幣
p.s 美國的零錢共有以下 5 種硬幣以及其面值：penny 1 cent, nickel 5 cents, dime 10 cents, quarter 25 cents, half-dollar 50 cents。
輸入說明：每組測試資料 1 列，有 1 個整數 n（0 <= n <= 7489），代表零錢的總金額（單位：cent）。
輸出說明：對每組測試資料請輸出共有多少種硬幣組合方式。請注意：n=0 我們算他是有一種方式。
| 範例輸入 #1 | 範例輸出 #1 |
|---|---|
| 0 17 11 4 |
1 6 4 1 |
這一題的硬幣可以重複選，所以跟 0/1 背包問題不太一樣，是多重背包問題的變形，來試試看吧。
#include <bits/stdc++.h> | |
using namespace std; | |
#define N 8000 | |
int n = 5, x, dp[N], coin[5] = {1, 5, 10, 25, 50}; | |
int main(){ | |
while (cin >> x){ | |
memset(dp,0,sizeof(dp)); | |
//dp [i][j]: 在使用前 i 個硬幣來達到組合成 j 的數量 | |
dp[0] = 1; // 0 本身不選任何數也是一種組合 | |
for (int i = 1; i <= n; i++){ | |
for (int j = coin[i-1]; j <= x; j++){ | |
dp[j] += dp[j - coin[i-1]]; | |
} | |
} | |
cout << dp[x] <<"\n"; | |
} | |
} |
先來看一下這個迴圈是正著跑的，前面我有提到為什麼背包問題要倒著跑，這個迴圈是正著跑就代表會計算到重覆選取同個東西的狀態。再來我們看看轉移式 dp[j] += dp[j - coin[i-1]]; 。
這個轉移式是選擇硬幣的時候的，如果硬幣的面額比 j 大那就代表放不進去那就不需要更新，需要更新的話就依據轉移式寫的來更新，現在這個硬幣可以放進來的時候就是 dp[i][j]=dp[i][j-現在這個硬幣的面額]+dp[i-1][j] 。
dp[i-1][j] 是甚麼意思，現在使用前 i 個硬幣組合數等於使用前 i-1 個硬幣的組合數在加上使用現在多了一個可以放入的硬幣的組合數，所以假設現在 dp[2][300]=20 代表使用兩種硬幣湊到 300 元有 20 種不同的組合方式，而現在 dp[3][300] 該怎麼計算出呢？就是原本的 20 種舊組合加上新組合的數量，新組合的數量怎麼算呢？ dp[3][300-新硬幣的面額(假設 87)] ，假設 dp[3][213]=15 那 dp[3][300] 就知道怎麼算了因為 dp[3][213] 有 15 種組合那就帶代表 15 種組合加上 87 會等於 300 這 15 種組合就是新的組合在加上原本舊的組合就可以算出我們要的答案了。
這題可以拿來跟 1-4 窮舉暴搜與回溯法 裡的窮舉解法對照 —— 用回溯法枚舉所有組合是 O(指數) ，用背包 DP 只要 O(nx) ，正是動態規劃「用空間換時間、避免重複計算」精神的最佳示範。
# 楊鐵心做 1 休 K（APCS）
楊鐵心帶著義女穆念慈做武術表演已經很久了，因為有些表演（例如胸口碎大石）實在很傷身體，所以現在每次表演完都要休息養傷。他接到許多的邀約，每天均有一場。每一場表演都可以得到某些金額的報酬，但是每次表演完至少要休息 K 天，請你協助他決定應該接受那些表演以得到最大的報酬。
| 範例一輸入 | 範例一輸出 |
|---|---|
| 5 1 1 2 3 1 5 |
9 |
這一題開始跟前面的題目有點不一樣，在列出轉移式可能不會像之前一樣那麼的直覺，可能會有一些細節的地方沒注意到就寫錯了，一開始寫錯了不要緊，要觀察錯誤的程式找出哪裡出了問題，並列出新的轉移式，列錯難免，最後有找到問題就好了。這一題我一開始寫的時候犯了一個小錯誤：
// [自己的解法，含錯誤示範] | |
#define N 100005 | |
int main(){ | |
int n,k,dp[N]; | |
cin>>n>>k; | |
for(int i=1;i<=n;i++){ | |
cin>>dp[i]; | |
if(i>k) | |
dp[i]=max(dp[i]+dp[i-k-1],dp[i-1]); | |
} | |
cout<<dp[n]; | |
} |
這一題的轉移式我沒有列錯： dp[i]=max(dp[i]+dp[i-k-1],dp[i-1]); ， dp[i] 代表在前 i 天的最佳解，這裡分別是選與不選取最大值。
來看看我程式中註解掉的迴圈： 2 1 1 7 7 7 10 10 。其實就是關鍵就在於直到 i>k 才開始進行選與不選的判斷，其實前 k 個也是要判斷的不過因為前 k 個如果選的話就是直接等於自己不用做更新，不選就是等於 dp[i-1] 個因為我們 dp 的定義是代表在前 i 天的最佳解。來看看修正後的程式：
#include <bits/stdc++.h> | |
using namespace std; | |
#define N 100005 | |
int dp[N]; | |
int main(){ | |
int n,k; | |
cin>>n>>k; | |
for(int i=1;i<=n;i++){ | |
cin>>dp[i]; | |
if(i<=k) | |
dp[i]=max(dp[i],dp[i-1]); | |
else if(i>k) | |
dp[i]=max(dp[i]+dp[i-k-1],dp[i-1]); | |
} | |
cout<<dp[n]; | |
} |
以下是正確的 dp 陣列內的值： 2 2 2 7 7 7 11 11 。
這個 bug 的教訓很有代表性：寫轉移式時，一定要問自己「邊界情況（這裡是 i≤k）有沒有被涵蓋到」。轉移式在 i 夠大時是對的，但如果沒有替小的 i 額外處理，程式的行為就會不符合 dp 陣列的定義。
# 周伯通的基地台（APCS，DP + 單調隊列優化）
周伯通開了一家通訊大廠並以他的名字命名，就叫做伯通公司，也有不少人弄錯了稱為博通。周伯通標下了一個政府標案，要在一條長長的大街架設基地台，長街被劃分成 n 個區段，編號依序為 1~n。在第 i 個區段架設基地台的話，需要成本 c [i]，而可以服務第 i-k 到第 i+k 的區段 (超出範圍可忽略)。現在輸入 k，要選一些區段架設基地台，以便每一個區段都可被服務到，請計算最少的總成本。
| 範例一輸入 | 範例一輸出 |
|---|---|
| 5 1 1 2 3 1 5 |
2 |
| 範例二輸入 | 範例二輸出 |
| 8 2 2 1 1 7 3 2 9 2 |
3 |
這一題的轉移式要特別注意，跟之前的題目不太一樣，小心不要搞混了，如果不太清楚就把題目多看幾次。
dp[i] 的定義是在 i 位置蓋基地台的最小成本。跟之前的「前 i 天的最佳解」不太一樣，這裡強調的是在 i 位置一定有蓋一個基地台，所以這裡的答案不一定是在最後。
dp[i] 需要從 dp[i-2k-1] 到 dp[i-1] 這段區間裡取最小值，再加上 c[i] 。如果每次都線性掃過這段區間找最小值，複雜度會變成 O(nk) ；用 ** 單調隊列（monotonic queue）** 維護區間最小值，可以把複雜度優化到 O(n) 。
我把利用雙向佇列（deque）的部分直接拉出來一個副程式我覺得這樣寫比較直覺，看起來應該也會比較輕鬆。
#include<bits/stdc++.h> | |
using namespace std; | |
#define N 2000005 | |
deque<int> min_d; | |
int a[N]; | |
long long dp[N]; | |
void put_min(int i){// 快速取最小值 | |
while(min_d.size()!=0 && dp[min_d.back()]>=dp[i]) | |
min_d.pop_back(); | |
min_d.push_back(i); | |
} | |
int main(){ | |
int n,k; | |
cin>>n>>k; | |
for(int i=0;i<n;i++) | |
cin>>a[i]; | |
dp[0]=a[0]; | |
put_min(0); | |
for(int i=1;i<=k;i++){ | |
dp[i]=a[i]; | |
put_min(i); | |
} | |
for(int i=k+1;i<n;i++){ | |
if(min_d.front()<=i-2*k-2) | |
min_d.pop_front(); | |
dp[i]=dp[min_d.front()]+a[i]; | |
put_min(i); | |
} | |
while(min_d.front()<=n-2-k) | |
min_d.pop_front(); | |
cout<<dp[min_d.front()]; | |
return 0; | |
} |
put_min 這個函式維護的正是 1-1 提過的單調隊列：deque 裡的元素對應的 dp 值永遠是遞增的，所以隊首永遠是目前視窗內的最小值。每次要放入新元素前，先把隊尾所有「比新元素還差」的元素踢掉 —— 因為它們比新元素舊、又比新元素差，未來不可能被選中。這樣一來，每個元素最多被放進、踢出各一次，整體均攤複雜度是 O(n) 。
# K 次買賣（106 高中全國賽 subtask，狀態機 DP）
某商品在某個時期每一天的價格是 p[1], p[2],…,p[n] 。假設只能先買後賣，且賣了之後才能再買，請計算買賣 K 次的最大獲利總價差，允許當天買賣，也就是不超過 K 次的買賣。
| 範例一輸入 | 範例一輸出 |
|---|---|
| 5 1 3 5 1 4 0 |
3 |
| 範例二輸入 | 範例二輸出 |
| 7 2 1 3 7 5 1 4 0 |
9 |
這一題我第一次在寫得候想了非常非常久。我們先來思考看看 k 固定為 1 的狀況，你或許會想到掃描線的解法，但是這裡嘗試用動態規劃的方式來思這個題目，前面有提到一個口訣選與不選，來看這個題目就變成，持有跟不持有。
來看看不持有的情況有兩種，一種就是跟之前一樣都沒有買，第二種則是因為本來持有而在這一天賣掉了變成了不持有：
dp[0][i]=max(dp[0][i-1],dp[1][i-1]+當天賣的價錢)
持有也有兩種情況，就是繼續持有跟本來不持有而今天買了這個股票變成持有。因為是買所以是用減的：
dp[1][i]=max(dp[1][i-1],dp[0][i-1]-當天賣的價錢)
dp[0][i] 代表第 i 天不持有的最佳解， dp[1][i] 代表第 i 天持有的最佳解。
#include<bits/stdc++.h> | |
using namespace std; | |
#define N 100005 | |
int p[N]={0}; | |
int main(){ | |
int n; | |
cin>>n; | |
for(int i=0;i<n;i++) | |
cin>>p[i]; | |
int dp1,dp2; | |
dp1 = 0;// 不持有 | |
dp2 = -p[0];// 持有 | |
for(int i=1;i<n;i++){ | |
// 現在不持有跟持有的情況 | |
dp1=max(dp1,dp2+p[i]); | |
dp2=max(dp2,-p[i]); | |
} | |
cout<<dp1; | |
} |
下列程式是把 k 加進來的完整解， dp[i][j] 的定義為前 i 次的買賣中第 j 次交易中不持有的最佳解：
#include<bits/stdc++.h> | |
using namespace std; | |
#define N 100001 | |
int p[N],dp[101][N]={0},buffer; | |
int main(){ | |
int n,k; | |
cin>>n>>k; | |
for(int i=0;i<n;i++) | |
cin>>p[i]; | |
for(int i=1;i<=k;i++){ | |
buffer = -p[0];// 持有 | |
for(int j=1;j<n;j++){ | |
dp[i][j]=max(dp[i][j-1], buffer +p[j]); | |
buffer=max(buffer,dp[i-1][j]-p[j]); | |
} | |
} | |
cout<<dp[k][n-1]; | |
} |
重點的改變在於這一行： buffer=max(buffer,dp[i-1][j]-p[j]); 。現在持有的最佳解，跟之前 k 只等於 1 情況不一樣，現在持有要考慮的狀況第一種是一樣的繼續持有就是不用更新值，第二種是買下現在的股票重點是買的錢是前一天不持有的錢的最佳解去減掉今天的價格。
這種「用兩個（或多個）變數描述當前的狀態」的 DP，叫做狀態機 DP，是 1D1D 分類裡很常見的一種形式：狀態不只是「位置」，還要加上「目前的狀態是什麼」（這裡是持有 / 不持有）。這個套路很值得記住，之後遇到「有限狀態轉換」類型的問題都可以往這個方向想。
# LIS（Longest Increasing Subsequence）：最長遞增子序列
# 一覽眾山小（AP325）
所謂「會當凌絕頂，一覽眾山小。」很多人都想爬到高處，為的是將群山看小，但是登高必自卑，行遠必自邇，最好是一步一步逐步往上，妄想一步登天的人往往摔的慘重。小說與遊戲中出現的人物往往都是越晚出現越厲害，現在已知所有人物的戰力與出場順序，想要找依照出場順序而且戰力逐步上升的人物序列，請你計算滿足這樣要求的序列的最大可能長度。
| 範例一輸入 | 範例一輸出 |
|---|---|
| 8 2 4 1 3 6 4 6 9 |
5 |
範例一說明：可以挑選子序列 (1,3,4,6,9)，長度為 5。
這一題是動態規劃的經典題目被稱為 LIS (longest Increasing subsequence) 最長遞增子序列等等看完程式碼之後就會知道位甚麼這題是經典了。
首先每個數字本身就是一個長度為 1 的子序列，接下來， dp[i] 表示以 nums[i] 結尾的最長遞增子序列的長度，我們從 i=1 開始遍歷 nums 數列。對於每個位置 i，我們再對 0 到 i-1 遍歷前面的元素，檢查是否存在 nums[j] < nums[i] 。如果存在，則表示可以將 nums[i] 加入到以 nums[j] 結尾的遞增子序列中，並更新 dp[i] 為 dp[j] + 1 （因為加入了一個元素）。最終，我們遍歷 dp 陣列，找到其中的最大值，即為最長遞增子序列的長度。以下為轉移式：
dp[i] = max(dp[i], dp[j] + 1) （對於所有 0 <= j < i 且 nums[j] < nums[i]）
這樣寫是 O(n^2) ，但如果搭配 1-3 搜尋技巧 提到的二分搜，可以優化到 O(n log n) ：
#include <bits/stdc++.h> | |
using namespace std; | |
#define N 200005 | |
vector<int> v; | |
int a[N],dp[N]; | |
int main(){ | |
int n; | |
cin>>n; | |
//dp [i] 紀錄 a [i] 改變了 v 的哪個位址 | |
for(int i=0;i<n;i++){ | |
cin>>a[i]; | |
auto it=lower_bound(v.begin(),v.end(),a[i]); | |
if(it == v.end()){ | |
v.push_back(a[i]); | |
dp[i]=v.size(); | |
}else{ | |
*it=a[i]; | |
dp[i]=it-v.begin()+1; | |
} | |
} | |
cout<<v.size()<<"\n";//ans | |
int ans[v.size()],k=0; | |
// 從最後跑回來可得最後出現的 LIS | |
// 注意從前面跑並不會得到最先出現的 LIS | |
for(int i=n-1,L=v.size();i>=0;i--){// 列出最後出現的 LIS | |
if(dp[i]==L){ | |
ans[k++]=a[i]; | |
L--; | |
} | |
} | |
for(--k;k>=0;k--) cout<<ans[k]<<" "; | |
} |
這裡用了一個技巧：維護一個陣列 v ， v[i] 表示「長度為 i+1 的遞增子序列中，結尾最小的那個值」。因為結尾越小，未來能接上的數字越多，所以這個值越小越好。每來一個新數字 a[i] ，用二分搜找到 v 中第一個不小於 a[i] 的位置並取代它（如果 a[i] 比所有元素都大，就直接接在後面）—— 這保證了 v 永遠是遞增的，可以持續用二分搜維護，複雜度降到 O(n log n) 。
我在最後列出了最後出現的 LIS。我們可以透過觀察 dp 陣列值的增加來找出最後出現的 LIS，可是如果從前往後跑要來找到最先出現的 LIS 你就會發現這是個錯誤，因為是從前面開始跑然而真正的 LIS 可能會在後面把前面的數替換掉，而你已經存足前面錯誤的數這樣就會導致程式出錯。
# 二維最大子矩陣（AP325，DP + 前綴和結合）
輸入一個 m×n 的二維整數矩陣 A [1:m][1:n]，要找一塊總和最大的連續子矩陣，輸出其總和。
| 範例輸入 #1 | 範例輸出 #1 |
|---|---|
| 3 4 2 -2 3 3 -6 5 2 -8 3 7 -2 4 |
13 |
這一題可以先從把題目想成一維的來思考。根據上一題提到的口訣「選與不選」，按照題目要求連續的子序列，這個子序列可能很包含一整個序列也可能只有一個數字。我們可以想成數字持續增加就選他反而會倒扣就不要了。
dp[i]=max(dp[i]+dp[i-1],0); // 以 i 結尾的字序列最大和
這其實就是 1-5 貪心演算法 跟 1-7 分治演算法 都解過的最大連續子陣列問題，這裡用 DP 的角度再看一次。
擴展到二維：利用前綴和的概念快速枚舉矩陣並且利用上述提到的轉移式，用動態規劃的方式減少不必要的窮舉。
#include<bits/stdc++.h> | |
using namespace std; | |
#define N 205 | |
int main(){ | |
int dp[N][N],mx=0,n,m; | |
cin>>n>>m; | |
for(int j=0;j<m;j++) dp[0][j]=0; | |
for(int i=1;i<=n;i++){ | |
for(int j=0,temp;j<m;j++){ | |
cin>>temp; | |
dp[i][j]=temp+dp[i-1][j]; | |
} | |
} | |
for(int i=1;i<=n;i++){ | |
for(int j=0;j<i;j++){ | |
int temp=0; | |
for(int k=0;k<m;k++){ | |
temp=max(dp[i][k]-dp[j][k]+temp,0); | |
mx=max(temp,mx); | |
} | |
} | |
} | |
cout<<mx; | |
} |
這個程式中的 dp 陣列只是利用前綴和的概念紀錄數值，實際上在計算子矩陣最大值的是 temp 這個變數，mx 則是在這些子矩陣最大值中找到最大值。 temp=max(dp[i][k]-dp[j][k]+temp,0); 可以發現這一行跟我們剛剛列的轉移式很像，這裡的 dp[i][k]-dp[j][k] 就是計算子矩陣然後加上 temp 在跟 0 比大小就是判斷子矩陣在以 k 為結尾的最大值。
所以結論就是利用了前綴和的概念快速窮舉矩陣並且利用上述提到的轉移式，利用動態規劃的方式減少不必要的窮舉。這題在動態規劃中是個經典的題目稱為連續子序列最大和問題。
# 刪除邊界（APCS，四維狀態的進階題）
一個矩陣的第一列與最後一列以及第一行與最後一行稱為該矩陣的四條邊界線，如果某一條邊界線的內容都是相同元素，則可以刪除該邊界線。如果一條邊界線的內容不完全相同，你可以修改某些格子讓邊界線的內容變成相同後，再刪除該邊界線。矩陣在刪除一條邊界線後，還是一個矩陣，但列數或行數會減少一，本題的目標是要重複執行修改與刪除邊界的動作，最後將整個矩陣刪除。輸入一個 0/1 矩陣，請計算最少要修改多少個元素才能將整個矩陣刪除。
| 範例一輸入 | 範例一輸出 |
|---|---|
| 4 5 0 1 0 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 1 0 |
2 |
這種題目也是我相對不擅長的題目，這種題目時間複雜度都很大，所以寫的時候不要緊張先看看測資的大小這題 m 跟 n 都不超過 25 所以可以放心。
這是 1D1D 甚至更高維度的極端例子：狀態需要用四個變數 (top, down, left, right) 描述當前剩下的子矩陣範圍，所以 dp 陣列開到四維。
#include <bits/stdc++.h> | |
using namespace std; | |
#define N 30 | |
int dp[N][N][N][N],m,n; | |
bool a[N][N]; | |
int f(int t,int d,int l,int r){//top down left right | |
if(t>d || l>r) return 0; | |
if(dp[t][d][l][r]>=0) return dp[t][d][l][r]; | |
int one=0,zero=0;//top | |
for(int i=l;i<=r;i++) | |
(a[t][i]?one++:zero++); | |
dp[t][d][l][r]=(one<zero ? one:zero)+f(t+1,d,l,r); | |
one=0;zero=0;//down | |
for(int i=l;i<=r;i++) | |
(a[d][i]?one++:zero++); | |
dp[t][d][l][r]=min(dp[t][d][l][r], | |
(one<zero ? one:zero)+f(t,d-1,l,r)); | |
one=0;zero=0;//left | |
for(int i=t;i<=d;i++) | |
(a[i][l]?one++:zero++); | |
dp[t][d][l][r]=min(dp[t][d][l][r], | |
(one<zero ? one:zero)+f(t,d,l+1,r)); | |
one=0;zero=0;//right | |
for(int i=t;i<=d;i++) | |
(a[i][r]?one++:zero++); | |
dp[t][d][l][r]=min(dp[t][d][l][r], | |
(one<zero ? one:zero)+f(t,d,l,r-1)); | |
return dp[t][d][l][r]; | |
} | |
int main(){ | |
cin>>m>>n; | |
memset(dp,-1,sizeof(dp)); | |
for(int i=0;i<m;i++) | |
for(int j=0;j<n;j++) | |
cin>>a[i][j]; | |
cout<<f(0,m-1,0,n-1); | |
} |
注意每個函式裡的每個 for 迴圈範圍都是根據每次遞迴狀況不同照每次 t,d,l,r 變數的變化再更動矩陣的範圍，注意 dp 陣列預設不能為 0，邊界條件也要注意，top 不能比 down 還下面，同理 left 不能比 right 還右邊。dp 陣列的定義就是現在那個矩陣的最佳解：
dp[t][d][l][r]=(one<zero ? one:zero)+f(t+1,d,l,r);
以這行為例就是現在算這行加上剩下的矩陣的最佳解，就會得到現在這個矩陣的最佳解，因為有四個邊所以會比四次取最小值。
這題告訴我們：DP 的維度不是固定的，取決於「唯一確定一個子問題」需要多少資訊。這裡子問題是「剩下的矩形範圍」，剛好需要四個座標，所以就要開四維陣列。
# 小結
這章篇幅很長，因為 DP 的變化真的很多，但核心心法從頭到尾沒變過：
- 定義轉移式：先想清楚
dp[...]代表什麼意思（子問題是什麼），這是最重要的一步 - 列出「選與不選」的所有可能：大部分 DP 都可以從這個角度切入
- 確認邊界條件跟終止條件：容易在這裡漏掉細節（見「楊鐵心做 1 休 K」的錯誤示範）
- 判斷 Top-Down 還是 Bottom-Up 比較好寫：轉移式直覺就用 Top-Down，效率優先就用 Bottom-Up
- 有需要的話做空間優化：滾動陣列（
O(nm)→O(m)）、單調隊列（O(nk)→O(n)）
用維度分類回顧這章的例題：
| 分類 | 例子 |
|---|---|
| 1D0D | 骰子、硬幣組合、置物櫃出租 |
| 2D0D | 0/1 背包、LCS、二維最大子矩陣 |
| 1D1D | 青蛙跳石頭、闖關二選一、K 次買賣（狀態機） |
| 座標型 | 方格棋盤路線 |
| 更高維 | 刪除邊界（四維） |
下一章要講基本圖論演算法 ——BFS、DFS、拓樸排序、Dijkstra、併查集。圖論題目常常會跟這章的 DP 結合（例如 DAG 上的最長路徑就是一種 DP），所以這章打好的「轉移式思維」在圖論裡也會繼續用到。
# 練習題
（之後補上）
