# Dynamic Programming by Colin --- ## Dynamic Programming (DP) 動態規劃 - DP = 分治 + 記憶化 - 分治：將⼤問題切成很多⼩問題，解決所有⼩問題也就解決⼤問題 - 記憶化：將算過的⼩問題答案記錄下來，再遇到就不⽤重新算（以空間換取時間） - dp就是⼀些用來降低解決問題時間複雜度的策略 - 通常需要通靈+大量練習 ---- ## DP解題步驟 1. 定義狀態：決定dp陣列中要儲存什麼東西 2. 想轉移式：想出遞迴式 3. 邊界條件：處理遞迴的起始與終止條件 4. 如何優化：如果會TLE就要思考如何優化時間複雜度 ---- - DP問題程式碼通常都很短，難的部分都是如何定義狀態或是最後的優化 - 需要大量練習來熟悉通靈方法 --- ## Example 1: 爬樓梯問題/費⽒數列 有⼀座$n$階的樓梯，⼀次可以向上跨1階或2階，請問有幾種⾛法可以⾛完這座階梯？（數字可能很⼤，請將答案對$10^9+7$取餘） $1\le n\le 10^6$，時間限制：$1s$ ---- - 模擬⼀下： ⾛上第1階時，只能從地⾯向上跨1階； ⾛上第2階時，可以從第1階向上跨1階，或是從地⾯向上跨2階； ⾛上第3階時，可以從第2階向上跨1階，或是從第1階向上跨2階； … ⾛上第n階時，可以從第n-1階向上跨1階，或是從第n-2階向上跨2階 ---- - 遞迴關係式： $f(i)$表示走到第$i$階的方法數 $f(i)=\begin{cases} 1 & \text {，} if\ i=1 \\ 2 & \text {，} if\ i=2 \\ f(i-1)+f(i-2) & \text {，} if\ i\ge 3 \end{cases}$ - 其實就是二階費式數列：前兩項之和等於第三項 - 可以寫一個簡單的遞迴程式 ---- code ```cpp= //直接遞迴 //O(2^n) #include <bits/stdc++.h> #define int long long #define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; int p=1e9+7; int f(int i){ if(i==1||i==2) return i; return (f(i-1)+f(i-2))%p; } signed main(){ int n; cin>>n; cout<<f(n)<<'\n'; return 0; } ``` ---- - 但是按照這個題目給的條件：$1\le n\le 10^6$，時間限制：$1s$ - 這份code在$n$很大時一定會TLE - 為啥? ----  ---- 由遞迴樹可以發現： - 有許多已經知道答案的遞迴狀態被重複執行，十分浪費時間 - 剛才的程式碼時間複雜度其實是$O(\varphi ^n)$ - $\varphi =\frac{\sqrt{5}+1}{2}\approx 1.618$，為黃金分割率 ---- 如何改善： - 可以把已經算過的遞迴狀態儲存起來，再遇到時就不用再算一次 ---- 1.定義狀態 - 定義$dp[n+1]$ - $dp[i]$表示走到第$i$階的方法數 ---- 2.想轉移式 - $dp[i]=dp[i-1]+dp[i-2]，i\ge 3$ ---- 3.邊界條件 - $dp[1]=1$ - $dp[2]=2$ - 最終答案是$dp[n]$ ---- 4.如何優化 - 有$n$個狀態 - 每次轉移只會用到前1項與前2項，故每次轉移是$O(1)$ - 總時間複雜度是$O(n)$，$1\le n\le 10^6$，可以在$1s$內完成 - 故不須優化 ---- code ```cpp= //dp(top down) //O(n) #include <bits/stdc++.h> #define int long long #define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; int p=1e9+7; vector<int> dp(1000005,-1); int f(int i){ if(dp[i]!=-1) return dp[i]; if(i==1||i==2) dp[i]=i; else dp[i]=(f(i-1)+f(i-2))%p; return dp[i]; } signed main(){ int n; cin>>n; cout<<f(n)<<'\n'; return 0; } ``` ---- code ```cpp= //dp(bottom up) //O(n) #include <bits/stdc++.h> #define int long long #define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; int p=1e9+7; vector<int> dp(1000005,-1); signed main(){ int n; cin>>n; dp[1]=1; dp[2]=2; for(int i=3;i<=n;i++) dp[i]=(dp[i-1]+dp[i-2])%p; cout<<dp[n]<<'\n'; return 0; } ``` ---- - dp可以分成top down與bottom up - top down是以遞迴的方式呈現，通常較為直覺(是遞迴轉移式的直接呈現)，但可能會有遞迴過深(stack overflow)的問題(基本上很少遇到) - bottom up是以迴圈的方式呈現，不會有遞迴過深的問題，但比較不直覺 ---- 練習題： [CSDC310 費氏數列(DP)](https://csdc.tw/problem/310/) ---- 補充： 費式數列可以用矩陣快速冪優化到$O(logn)$ --- ## Example 2: 神偷大盜 [CSDC256 神偷大盜](https://csdc.tw/problem/256/) 有⼀位⼤盜想在⼀條有$n$間房⼦的街道上偷東⻄，會給你⼀串正整數$a[i]$分別代表第$1$~$n$間房⼦的財產總額，不能連續偷兩間相鄰的房⼦，請問這位⼤盜最多能偷到多少錢？ $1\le n\le 10^6$，時間限制：$1s$ ---- 1.定義狀態 - 定義$dp[n+1]$ - $dp[i]$表示考慮$1$~$i$，偷第$i$間房子可以獲得的最大值 ---- 2.想轉移式 - $dp[i]=max(dp[j])+a[i]，1\le j\le i-2$ ---- 3.邊界條件 - $dp[1]=a[1]$ - $dp[2]=a[2]$ ---- 4.如何優化 - 有$n$個狀態 - 每次轉移會用到前$i-2$項，故每次轉移是$O(n)$ - 總時間複雜度是$O(n^2)$，$1\le n\le 10^6$，無法在$1s$內完成 - 故需要優化 ---- - 觀察轉移式 - $dp[i]=max(dp[j])+a[i]，1\le j\le i-2$ - 每次轉移真的需要從$dp[1]$考慮到$dp[i-2]$嗎 ---- - 題⽬有說每間房⼦的財產總額必為正整數 - $dp[3]=dp[1]+a[3]$，可得$dp[3]$必大於$dp[1]$ - $dp[4]=max(dp[1],dp[2])+a[4]$，可得$dp[4]$必大於$dp[1]$和$dp[2]$ - $dp[5]=max(dp[1],dp[2],dp[3])+a[5]$，由上述可知轉移式根本不需要考慮$dp[1]$ - $dp[6]=max(dp[1],dp[2],dp[3],dp[4])+a[6]$，由上述可知轉移式根本不需要考慮$dp[1]$和$dp[2]$ ---- - 依此類推，轉移式可以改成： - $dp[i]=max(dp[i-2],dp[i-3])+a[i]$ - 有$n$個狀態 - 每次轉移只會用到前2項與前3項，故每次轉移是$O(1)$ - 總時間複雜度是$O(n)$，$1\le n\le 10^6$，可以在$1s$內完成 ---- - 邊界條件： - $dp[1]=a[1]$ - $dp[2]=a[2]$ - $dp[3]=dp[1]+a[3]$ - 最終答案是$max(dp[n],dp[n-1])$ ---- code ```cpp= //dp(top down) //O(n) #include <bits/stdc++.h> #define int long long #define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; int n,a[1000005]; vector<int> dp(1000005,-1); int f(int i){ if(dp[i]!=-1) return dp[i]; if(i==1||i==2) dp[i]=a[i]; else if(i==3) dp[i]=f(1)+a[3]; else dp[i]=max(f(i-2),f(i-3))+a[i]; return dp[i]; } signed main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; cout<<max(f(n),f(n-1))<<'\n'; return 0; } ``` ---- code ```cpp= //dp(bottom up) //O(n) #include <bits/stdc++.h> #define int long long #define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; int n,a[1000005]; vector<int> dp(1000005,-1); signed main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; dp[1]=a[1]; dp[2]=a[2]; dp[3]=dp[1]+a[3]; for(int i=4;i<=n;i++) dp[i]=max(dp[i-2],dp[i-3])+a[i]; cout<<max(dp[n],dp[n-1])<<'\n'; return 0; } ``` --- ## Example 3: 棋盤捷徑問題 [AtCoder DP Contest H - Grid 1](https://atcoder.jp/contests/dp/tasks/dp_h) [CSES Grid Paths](https://cses.fi/problemset/task/1638) 輸入兩正整數$n$,$m$，以及⼀個棋盤⽅格$a[n][m]$，若$a[i][j]$是'.'表示可以通⾏，若$a[i][j]$是'\*'表示是障礙物，請問從棋盤⽅格的左上⾓⾛到右下⾓，只能向右或向下，有幾種⾛法？（數字可能很⼤，請將答案對$10^9+7$取餘） $2\le n,m\le 10^3$，時間限制：$1s$ ---- 1.定義狀態 - 定義$dp[n+1][m+1]$ - $dp[i][j]$表示走到$a[i][j]$的方法數 ---- 2.想轉移式 - $dp[i][j]=\begin{cases} 0 & \text {，} if\ a[i][j]='*' \\ dp[i-1][j]+dp[i][j-1] & \text {，} if\ a[i][j]='.' \\ \end{cases}$ ---- 3.邊界條件 - $dp[1][1]=\begin{cases} 0 & \text {，} if\ a[i][j]='*' \\ 1 & \text {，} if\ a[i][j]='.' \\ \end{cases}$ - $dp[1][j]=\begin{cases} 0 & \text {，} if\ a[1][j]='*' \\ dp[1][j-1] & \text {，} if\ a[1][j]='.' \\ \end{cases}$ - $dp[i][1]=\begin{cases} 0 & \text {，} if\ a[i][1]='*' \\ dp[i-1][1] & \text {，} if\ a[i][1]='.' \\ \end{cases}$ - 最終答案是$dp[n][m]$ ---- 4.如何優化 - 有$nm$個狀態 - 每次轉移是$O(1)$ - 總時間複雜度是$O(nm)$ - 不須優化 ---- code ```cpp= //dp(bottom up) //O(hw) #include <bits/stdc++.h> #define int long long #define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; const int p=1e9+7; int h,w,dp[1005][1005]; char arr[1005][1005]; signed main(){ //horaceorz; cin>>h>>w; for(int i=1;i<=h;i++) for(int j=1;j<=w;j++) cin>>arr[i][j]; dp[1][1]=1; for(int i=2;i<=h;i++) dp[i][1]=(arr[i][1]=='.'?dp[i-1][1]:0); for(int i=2;i<=w;i++) dp[1][i]=(arr[1][i]=='.'?dp[1][i-1]:0); for(int i=2;i<=h;i++){ for(int j=2;j<=w;j++){ dp[i][j]=(arr[i][j]=='.'?(dp[i-1][j]+dp[i][j-1])%p:0); } } cout<<dp[h][w]<<'\n'; return 0; } ``` --- ## Example 4: 假期計畫 [AtCoder DP Contest C - Vacation](https://atcoder.jp/contests/dp/tasks/dp_c) 有⼀個$n$天的假期，每天只能做A,B,C三項活動中的其中⼀種，但不可以連續兩天做相同的活動。已知第$i$天做這三項活動可以獲得的滿⾜感分別是$a[i]$,$b[i]$,$c[i]$，請問假期結束時可以獲得的最⼤滿⾜感是多少？ $1\le n\le 10^5$，時間限制：$1s$ ---- - 窮舉時間複雜度是$O(3^n)$，一定會TLE - 所以要用DP處理 ---- 1.定義狀態 - 定義$dp[n+1][3]$ - $dp[i][0]$表示考慮$1$~$i$，第$i$天做A活動可以獲得的最⼤滿⾜感 - $dp[i][1]$表示考慮$1$~$i$，第$i$天做B活動可以獲得的最⼤滿⾜感 - $dp[i][2]$表示考慮$1$~$i$，第$i$天做C活動可以獲得的最⼤滿⾜感 ---- 2.想轉移式 - $dp[i][0]=max(dp[i-1][1],dp[i-1][2])+a[i]$ - $dp[i][1]=max(dp[i-1][0],dp[i-1][2])+b[i]$ - $dp[i][2]=max(dp[i-1][0],dp[i-1][1])+c[i]$ ---- 3.邊界條件 - $dp[1][0]=a[1]$ - $dp[1][1]=b[1]$ - $dp[1][2]=c[1]$ - 最終答案是$max(dp[n][0],dp[n][1],dp[n][2])$ ---- 4.如何優化 - 有$3n$個狀態 - 每次轉移是$O(1)$ - 總時間複雜度是$O(n)$ - 不須優化 ---- code ```cpp= //dp(top down) //O(n) #include <bits/stdc++.h> #define int long long #define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; int n,a[100005],b[100005],c[100005]; vector<vector<int>> dp(100005,vector<int>(3,-1)); int f(int i,int j){ if(dp[i][j]!=-1) return dp[i][j]; if(i==1){ if(j==0) dp[i][j]=a[1]; else if(j==1) dp[i][j]=b[1]; else dp[i][j]=c[1]; }else{ if(j==0) dp[i][j]=max(f(i-1,1),f(i-1,2))+a[i]; else if(j==1) dp[i][j]=max(f(i-1,0),f(i-1,2))+b[i]; else dp[i][j]=max(f(i-1,0),f(i-1,1))+c[i]; } return dp[i][j]; } signed main(){ //horaceorz; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]>>b[i]>>c[i]; cout<<max(max(f(n,0),f(n,1)),f(n,2))<<'\n'; return 0; } ``` ---- code ```cpp= //dp(bottom up) //O(n) #include <bits/stdc++.h> #define int long long #define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; int n,a[100005],b[100005],c[100005]; vector<vector<int>> dp(100005,vector<int>(3,-1)); signed main(){ //horaceorz; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]>>b[i]>>c[i]; dp[1][0]=a[1]; dp[1][1]=b[1]; dp[1][2]=c[1]; for(int i=2;i<=n;i++){ dp[i][0]=max(dp[i-1][1],dp[i-1][2])+a[i]; dp[i][1]=max(dp[i-1][0],dp[i-1][2])+b[i]; dp[i][2]=max(dp[i-1][0],dp[i-1][1])+c[i]; } cout<<max(max(dp[n][0],dp[n][1]),dp[n][2])<<'\n'; return 0; } ``` --- ## Example 5: 0/1背包問題 [AtCoder DP Contest D - Knapsack 1](https://atcoder.jp/contests/dp/tasks/dp_d) 有⼀個可以耐重$W$的背包，及$N$種物品，每種物品有各⾃的重量$w[i]$、價值 $v[i]$，**且都只有⼀個**，求在不超過重量限制的情況下往背包塞盡量多的東⻄，總價值最⼤為多少? $1\le N\le 100$，$1\le W\le 10^5$，時間限制：$1s$ ---- 1.定義狀態 - 定義$dp[N+1][W+1]$ - $dp[i][j]$表示考慮到第$i$種物品且剩下空間為$j$時所能放入的最⼤價值 ---- 2.想轉移式 - $dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])$，$j\ge w[i]$ - $dp[i][j]=dp[i-1][j]$，$j<w[i]$ ---- 3.邊界條件 - $dp[1][0]=0$ - 最終答案是$dp[N][W]$ ---- 4.如何優化 - 有$NW$個狀態 - 每次轉移是$O(1)$ - 總時間複雜度是$O(NW)$ - 不須優化 ---- code ```cpp= //0/1背包問題 //dp(bottom up) //時間複雜度:O(NW) //空間複雜度:O(NW) #include <bits/stdc++.h> #define int long long #define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; int N,W,w[105],v[105]; vector<vector<int>> dp(105,vector<int>(100005,0)); signed main(){ //horaceorz; cin>>N>>W; for(int i=1;i<=N;i++) cin>>w[i]>>v[i]; for(int i=1;i<=N;i++){ for(int j=1;j<=W;j++){ if(j>=w[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]); else dp[i][j]=dp[i-1][j]; } } cout<<dp[N][W]<<'\n'; return 0; } ``` ---- code ```cpp= //0/1背包問題 //dp(bottom up)+滾動數組優化 //時間複雜度:O(NW) //空間複雜度:O(W) #include <bits/stdc++.h> #define int long long #define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; int N,W,w[105],v[105]; vector<int> dp(100005,0); signed main(){ //horaceorz; cin>>N>>W; for(int i=1;i<=N;i++) cin>>w[i]>>v[i]; for(int i=1;i<=N;i++){ for(int j=W;j>=w[i];j--){ dp[j]=max(dp[j],dp[j-w[i]]+v[i]); } } cout<<dp[W]<<'\n'; return 0; } ``` ---- 延伸題 [CSES Minimizing Coins 換零錢問題](https://cses.fi/problemset/task/1634/) ---- AC code ```cpp= //dp(top down) //O(nx) #include <bits/stdc++.h> #define int long long #define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; int n,x,a[105],dp[1000005]; int f(int x){ if(dp[x]==INT_MAX){ if(x==0){ dp[x]=0; }else{ int mini=INT_MAX; for(int i=0;i<n;i++){ if(x>=a[i]) mini=min(mini,f(x-a[i])); } dp[x]=mini+1; } } return dp[x]; } signed main(){ //horaceorz; cin>>n>>x; for(int i=0;i<=x;i++) dp[i]=INT_MAX; for(int i=0;i<n;i++) cin>>a[i]; int ans=f(x); if(dp[0]!=0) cout<<-1; else cout<<ans; return 0; } ``` ---- AC code ```cpp= //dp(bottom up) //O(nx) #include <bits/stdc++.h> #define int long long #define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; int n,x,a[105],dp[1000005]; signed main(){ //horaceorz; cin>>n>>x; for(int i=0;i<=x;i++) dp[i]=INT_MAX; for(int i=0;i<n;i++) cin>>a[i]; dp[0]=0; for(int i=0;i<n;i++){ for(int j=a[i];j<=x;j++){ dp[j]=min(dp[j],dp[j-a[i]]+1); } } if(dp[x]!=INT_MAX) cout<<dp[x]; else cout<<-1; return 0; } ``` --- ## Example 6: 無限背包問題 [AtCoder DP Contest D - Knapsack 1](https://atcoder.jp/contests/dp/tasks/dp_d) 有⼀個可以耐重$W$的背包，及$N$種物品，每種物品有各⾃的重量$w[i]$、價值 $v[i]$，**且都有無限個**，求在不超過重量限制的情況下往背包塞盡量多的東⻄，總價值最⼤為多少? $1\le N\le 100$，$1\le W\le 10^5$，時間限制：$1s$ ---- 1.定義狀態 - 定義$dp[N+1][W+1]$ - $dp[i][j]$表示考慮到第$i$種物品且剩下空間為$j$時所能放入的最⼤價值 ---- 2.想轉移式 - $dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i])$，$j\ge w[i]$ - $dp[i][j]=dp[i-1][j]$，$j<w[i]$ ---- 3.邊界條件 - $dp[1][0]=0$ - 最終答案是$dp[N][W]$ ---- 4.如何優化 - 有$NW$個狀態 - 每次轉移是$O(1)$ - 總時間複雜度是$O(NW)$ - 不須優化 ---- code ```cpp= //無限背包問題 //dp(bottom up) //時間複雜度:O(NW) //空間複雜度:O(NW) #include <bits/stdc++.h> #define int long long #define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; int N,W,w[105],v[105]; vector<vector<int>> dp(105,vector<int>(100005,0)); signed main(){ //horaceorz; cin>>N>>W; for(int i=1;i<=N;i++) cin>>w[i]>>v[i]; for(int i=1;i<=N;i++){ for(int j=1;j<=W;j++){ if(j>=w[i]) dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]); else dp[i][j]=dp[i-1][j]; } } cout<<dp[N][W]<<'\n'; return 0; } ``` ---- code ```cpp= //無限背包問題 //dp(bottom up)+滾動數組優化 //時間複雜度:O(NW) //空間複雜度:O(W) #include <bits/stdc++.h> #define int long long #define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; int N,W,w[105],v[105]; vector<int> dp(100005,0); signed main(){ //horaceorz; cin>>N>>W; for(int i=1;i<=N;i++) cin>>w[i]>>v[i]; for(int i=1;i<=N;i++){ for(int j=w[i];j<=W;j++){ dp[j]=max(dp[j],dp[j-w[i]]+v[i]); } } cout<<dp[W]<<'\n'; return 0; } ``` --- ## Example 7: LIS [CSES Increasing Subsequence](https://cses.fi/problemset/task/1145) LIS是最⻑遞增⼦序列（Longest Increasing Subsequence），給定⼀個⻑度為$n$的序列$a[n]$，請輸出這個序列的最⻑遞增⼦序列（嚴格遞增）的⻑度。 $1\le n\le 10^5$，時間限制：$1s$ ---- - ⼦序列：把原本的序列刪掉其中幾項，並把剩下的項依照原本的順序排好。 （例如：ace、bcde、b、空集合、abcde 等都是 abcde 的⼦序列） - 嚴格遞增⼦序列：每⼀項都⼤於前⼀項的⼦序列 - 不嚴格遞增⼦序列：每⼀項都⼤於等於前⼀項的⼦序列 （例如：1,2,3,4,5 是 1,5,2,9,2,3,4,5,1,5 的嚴格遞增⼦序列； 1,2,2,3,4,5,5 是 1,5,2,9,2,3,4,5,6,5 的不嚴格遞增⼦序列） ---- 1.定義狀態 - 定義$dp[n+1]$ - $dp[i]$表示前$i$項的LIS長度 ---- 2.想轉移式 - $dp[i]=max(dp[j])+1$，$j<i$且$a[j]<a[i]$ ---- 3.邊界條件 - $dp[1]=1$ - 最終答案是$dp[n]$ ---- 4.如何優化 - 有$n$個狀態 - 每次轉移是$O(n)$ - 總時間複雜度是$O(n^2)$，會TLE - 需要優化 ---- 重新定義狀態!!! - 定義$dp[n+1]$ - $dp[i]$儲存長度為$i$的LIS的第$i$項數字的最小值，預設為正無窮 ---- code ```cpp= //嚴格遞增LIS //O(nlogn) #include <bits/stdc++.h> #define int long long #define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; int n,a[100005]; vector<int> dp(100005,1e18); signed main(){ //horaceorz; cin>>n; for(int i=0;i<n;i++) cin>>a[i]; for(int i=0;i<n;i++){ int j=lower_bound(dp.begin(),dp.end(),a[i])-dp.begin(); dp[j]=a[i]; } cout<<lower_bound(dp.begin(),dp.end(),1e18)-dp.begin()<<'\n'; return 0; } ``` ---- code ```cpp= //非嚴格遞增LIS //O(nlogn) #include <bits/stdc++.h> #define int long long #define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; int n,a[100005]; vector<int> dp(100005,1e18); signed main(){ //horaceorz; cin>>n; for(int i=0;i<n;i++) cin>>a[i]; for(int i=0;i<n;i++){ int j=upper_bound(dp.begin(),dp.end(),a[i])-dp.begin(); dp[j]=a[i]; } cout<<lower_bound(dp.begin(),dp.end(),1e18)-dp.begin()<<'\n'; return 0; } ``` ---- 嚴格遞增=>lower_bound 不嚴格遞增=>upper_bound ---- 延伸題 [2021.01 APCS 4. 飛黃騰達](https://zerojudge.tw/ShowProblem?problemid=f608) ---- AC code ```cpp= #include <bits/stdc++.h> #define int long long #define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; signed main(){ //horaceorz; int n; cin>>n; int dp[n]; pair<int,int> p[n]; for(int i=0;i<n;i++){ dp[i]=1e18; cin>>p[i].first>>p[i].second; } sort(p,p+n); for(int i=0;i<n;i++){ int j=upper_bound(dp,dp+n,p[i].second)-dp; dp[j]=p[i].second; } cout<<lower_bound(dp,dp+n,1e18)-dp; return 0; } ``` --- ## Example 8: LCS LCS是最⻑共同⼦序列（Longest Common Subsequence），給定兩個⻑度分別為$N$,$M$的字串A,B，請輸出這兩個字串最⻑共同⼦序列的⻑度。 $1\le N,M\le 1000$，時間限制：$1s$ ---- - 共同⼦序列：同時是兩個序列的⼦序列的序列。 （例如：ab、ac、abd、空集合、abc 等都是 abcde 和 abedc 的共同⼦序列） ---- 1.定義狀態 - 定義$dp[N+1][M+1]$ - $dp[i][j]$表示考慮A前$i$項與B前$j$項的LCS長度 ---- 2.想轉移式 - $dp[i][j]=dp[i-1][j-1]+1$，$A[i]=B[j]$ - $dp[i][j]=max(dp[i-1][j],dp[i][j-1])$，$A[i]\not =B[j]$ ---- 3.邊界條件 - $dp[i][0]=dp[0][j]=0$ - 最終答案是$dp[N][M]$ ---- 4.如何優化 - 有$NM$個狀態 - 每次轉移是$O(1)$ - 總時間複雜度是$O(NM)$ - 不須優化 ---- code ```cpp= //dp(top down) //O(NM) #include <bits/stdc++.h> #define int long long #define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; int N,M; string A,B; vector<vector<int>> dp(1005,vector<int>(1005,-1)); int f(int i,int j){ if(dp[i][j]!=-1) return dp[i][j]; if(i==0||j==0) dp[i][j]=0; else if(A[i-1]==B[j-1]) dp[i][j]=f(i-1,j-1)+1; else dp[i][j]=max(f(i-1,j),f(i,j-1)); return dp[i][j]; } signed main(){ cin>>N>>M>>A>>B; cout<<f(N,M)<<'\n'; return 0; } ``` ---- 延伸題 [CSES Edit Distance 編輯距離](https://cses.fi/problemset/task/1639) ---- AC code ```cpp= //dp(top down) #include <bits/stdc++.h> #define int long long #define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; string a,b; int dp[5005][5005]; int f(int i,int j){ if(dp[i][j]!=INT_MAX) return dp[i][j]; if(i==0&&j==0) dp[i][j]=0; else if(i==0) dp[i][j]=j; else if(j==0) dp[i][j]=i; else if(a[i-1]==b[j-1]) dp[i][j]=f(i-1,j-1); else dp[i][j]=min(min(f(i-1,j)+1,f(i,j-1)+1),f(i-1,j-1)+1); return dp[i][j]; } signed main(){ //horaceorz; cin>>a>>b; for(int i=0;i<=a.size();i++) for(int j=0;j<=b.size();j++) dp[i][j]=INT_MAX; cout<<f(a.size(),b.size()); return 0; } ``` --- ## Example 9: 石子合併 [AtCoder DP Contest N - Slimes](https://atcoder.jp/contests/dp/tasks/dp_n) 有$n$堆石子排成一排，已知每堆石子的重量。每次只能合併相鄰的兩堆石子，合併的花費為兩堆石子的總重，若要將全部的石子合併成一堆，求最少的總花費。 $2\le n\le 400$，時間限制：$1s$ ---- 1.定義狀態 - 定義$dp[n+1][n+1]$ - $dp[i][j]$表示合併第$i$堆到第$j$堆石子所需最少花費，$i\le j$ ---- 2.想轉移式 - $dp[i][j]=min(dp[i][k]+dp[k+1][j])+w(i,j)$ - $i\le k<j$ - $w(i,j)$表示第$i$堆到第$j$堆石子的總重，可以用前綴和預處理 ---- 3.邊界條件 - $dp[i][i]=0$ - 最終答案是$dp[1][n]$ ---- 4.如何優化 - 有$n^2$個狀態 - 每次轉移是$O(n)$ - 總時間複雜度是$O(n^3)$ - $2\le n\le 400$，時間限制：$1s$ - 不須優化 ---- code ```cpp= //dp(top down) //O(n^3) #include <bits/stdc++.h> #define int long long #define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; int n,arr[1005],p[1005],dp[1005][1005]; int w(int i,int j){ return p[j]-p[i-1]; } int f(int i,int j){ if(i==j) return 0; if(dp[i][j]!=1e18) return dp[i][j]; for(int k=i;k<j;k++){ dp[i][j]=min(dp[i][j],f(i,k)+f(k+1,j)+w(i,j)); } return dp[i][j]; } signed main(){ //horaceorz; cin>>n; p[0]=0; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++) dp[i][j]=1e18; cin>>arr[i]; p[i]=p[i-1]+arr[i]; } cout<<f(1,n)<<'\n'; return 0; } ``` ---- code ```cpp= //dp(bottom up) //O(n^3) #include <bits/stdc++.h> #define int long long #define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; int n,arr[1005],p[1005],dp[1005][1005]; int w(int i,int j){ return p[j]-p[i-1]; } signed main(){ //horaceorz; cin>>n; p[0]=0; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(i==j) dp[i][j]=0; else dp[i][j]=1e18; } cin>>arr[i]; p[i]=p[i-1]+arr[i]; } for(int len=2;len<=n;len++){ for(int i=1;i<=n-len+1;i++){ int j=i+len-1; for(int k=i;k<j;k++){ dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+w(i,j)); } } } cout<<dp[1][n]<<'\n'; return 0; } ``` ---- 補充： 石子合併可以用四邊形不等式優化到$O(n^2)$ ---- 延伸題 [2024.01 APCS 4. 合併成本](https://zerojudge.tw/ShowProblem?problemid=m934) ---- AC code ```cpp= //dp(top down) //O(n^3) #include <bits/stdc++.h> #define int long long #define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; int n,arr[105],p[105],dp[105][105]; int w(int i,int j){ return p[j]-p[i-1]; } int f(int i,int j){ if(i==j) return 0; if(dp[i][j]!=1e18) return dp[i][j]; for(int k=i;k<j;k++){ dp[i][j]=min(dp[i][j],f(i,k)+f(k+1,j)+abs(w(i,k)-w(k+1,j))); } return dp[i][j]; } signed main(){ //horaceorz; cin>>n; p[0]=0; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++) dp[i][j]=1e18; cin>>arr[i]; p[i]=p[i-1]+arr[i]; } cout<<f(1,n)<<'\n'; return 0; } ``` ---- AC code ```cpp= //dp(bottom up) //O(n^3) #include <bits/stdc++.h> #define int long long #define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; int n,arr[105],p[105],dp[105][105]; int w(int i,int j){ return p[j]-p[i-1]; } signed main(){ //horaceorz; cin>>n; p[0]=0; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(i==j) dp[i][j]=0; else dp[i][j]=1e18; } cin>>arr[i]; p[i]=p[i-1]+arr[i]; } for(int len=2;len<=n;len++){ for(int i=1;i<=n-len+1;i++){ int j=i+len-1; for(int k=i;k<j;k++){ dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+abs(w(i,k)-w(k+1,j))); } } } cout<<dp[1][n]<<'\n'; return 0; } ``` --- ## Example 10: 位元問題 [AtCoder DP Contest S - Digit Sum](https://atcoder.jp/contests/dp/tasks/dp_s) 求$1$~$K$內數字符合所有位元之和為$D$的倍數的數字數量。 $1\le \vert K\vert \le 10^4$，$1\le D\le 100$，時間限制：$1s$ ---- 1.定義狀態 - 定義$dp[\vert K\vert +1][2][D]$ - $dp[i][0][j]$表示考慮到第$i$位，第$1$~$i$位數字總和mod $D$為$j$的數量 - $dp[i][1][j]$表示考慮到第$i$位，第$1$~$i$位數字總和mod $D$為$j$且<原第$1$~$i$位數字的數量 ---- 2.想轉移式 - $dp[i][0][j]=\sum(dp[i-1][0][x])$，$(x+0$~$9)$ mod $D=j$ - $dp[i][1][j]=\sum(dp[i-1][0][x])+\sum(dp[i-1][1][y])$，$(x+0$~$K[i]-1)$ mod $D=j$，$(y+K[i])$ mod $D=j$ ---- 3.邊界條件 - $dp[1][0][(0$~$9) mod D]=1$ - $dp[1][1][(0$~$K[1]) mod D]=1$ - 最終答案是$dp[\vert K\vert][1][0]-1$ (要扣掉0) ---- 4.如何優化 - 有$\vert K\vert \times D$個狀態 - 每次轉移是$O(1)$ - 總時間複雜度是$O(\vert K\vert \times D)$ - 不須優化 ---- code ```cpp= //digit dp //O(|k|*d) #include <bits/stdc++.h> #define int long long #define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; const int prime=1e9+7; string k; int d,dp[10005][2][105]; signed main(){ //horaceorz; cin>>k>>d; int len=k.size(); for(int i=0;i<len/2;i++) swap(k[i],k[len-i-1]); for(int j=0;j<d;j++){ dp[1][0][j]=0; dp[1][1][j]=0; } for(int m=0;m<=9;m++) dp[1][0][m%d]++; for(int m=0;m<=k[0]-'0';m++) dp[1][1][m%d]++; for(int i=1;i<=len;i++){ for(int j=0;j<d;j++){ for(int m=0;m<=9;m++){ dp[i+1][0][(m+j)%d]+=dp[i][0][j]; dp[i+1][0][(m+j)%d]%=prime; } for(int m=0;m<k[i]-'0';m++){ dp[i+1][1][(m+j)%d]+=dp[i][0][j]; dp[i+1][1][(m+j)%d]%=prime; } dp[i+1][1][(k[i]-'0'+j)%d]+=dp[i][1][j]; dp[i+1][1][(k[i]-'0'+j)%d]%=prime; } } cout<<(dp[len][1][0]-1+prime)%prime<<'\n'; return 0; } ``` --- 練習資源 [AtCoder DP Contest](https://atcoder.jp/contests/dp/tasks) [CSES](https://cses.fi/problemset/list/) [CSDCOJ dp](https://csdc.tw/problems/?tag=dp) [LeetCode dp](https://leetcode.com/problemset/?topicSlugs=dynamic-programming&page=1) --- Thank you for listening!