Introduction to Competitive Programming
2/8
動態規劃。你當下問題的答案會隨著你解決小問題的時候時刻更新著大問題
DP題通常難以被其他算法取代,且題型多種多樣。
為什麼會說DP是通靈則是因為一定程度的題目通常轉移式都不好求,很吃你的直覺。
遇到DP題的頻率大概為1題/場,但 台灣站 3-5 題/場,因此若是你DP很強可以拿去說嘴很久。
通常在dp裡面,總是可以找到當前狀態的前幾個狀態合併成為當前狀態,而特性如下。
根據以上幾點,尋找到問題之間的關係後,即可分割成小問題去進行求解,求解過程主要是對小問題進行解答後,在根據小問題的答案進行下一步操作。
分別有兩種方式
先看過兩題例題,為經典的記憶化搜索
例題Q1 單條鏈數學式求解
給你 \(q\) 次詢問 每次給定數字\(n\) 詢問 \(n!\) 為多少
根據前面的步驟,會發現 \(n!\) 跟 \(n-1\) 的關係為 \((n-1)! * n\)
所以就可以分割為 \(1,2,3,.......n-1,n\)
設計方法則為 每一層是前一層*當前層數[ \((n-1)! * n\) ]
實作方法則在下面做出簡單的範例
void factorial(){ f[0] = 0;f[1] = 1; for (int i=2; i<=N; i++) f[i] = f[i-1] * i; }
分析例題一的時間複雜度以及空間複雜度
時間複雜度 : 總共 N 個問題,每個問題花費 O(1) 時間,總共花費 O(N) 時間。
空間複雜度 : 求 1! 到 N!,總共 N 個問題,用一條 N 格陣列儲存全部問題的答案,空間複雜度 O(N)
\(q\) 筆詢問 \(1\) \(\le q \le 2*10^5\)
每筆詢問給予一個數字 \(n\) (\(1\) \(\le n \le 10^6\)) , 求 \(f [ n ]\) 值為多少
思路
首先我們分析暴力做他的時間複雜度。
發現到這樣直接暴力解訪問f(n-2)+f(n-1)做會錯。
只需要開一個\(10^6\)的大小然後 \(dp[i]\) 儲存 \(f(i)\) 的結果就好,具體代碼如下。
top-down
int f(int n){
if (n == 0 || n == 1) return 1;
// 用 0 代表該問題還未計算答案
if (table[n]) return table[n];
return table[n] = f(n-1) + f(n-2);
}
int main(){
f(N);
int q;
while(cin>>q)){
cout<<f(q)<<'\n';
}
}
Bottom-up
int main(){
table[0] = 1;
table[1] = 1;
for (int i=2; i<=N; i++)
table[i] = table[i-1] + table[i-2];
int q;
while(cin>>q)){
cout<<f(q)<<'\n';
}
}
分析例題二的時間複雜度以及空間複雜度
時間複雜度 : 總共 N 個問題,每個問題花費 O(1) 時間,總共花費 O(N) 時間。
空間複雜度 : 求 1 到 N,總共 N 個問題,用一條 N 格陣列儲存全部問題的答案,空間複雜度 O(N)
簡單的時間複雜度 : 狀態數*轉移複雜度
難的時間複雜度 : 根據每個人會有不同的實作方式去計算
狀態數 : 計算最終答案總共需要用到的子問題數量
轉移複雜度 : 計算任一個子問題的複雜度
空間複雜度 : 很直觀根據你開了多少來確定,應該不用太多描述。
\(f(n)=f(n-1)+f(n-2)\) –- 遞迴數學式問題
\(dp[i]=\max\limits_{0\le j\lt i,i-j<=k}\{dp[j]+a[i]\}\) –- 單調隊列優化
\(dp[i][j]=\max({dp[i-1][j],dp[i-1][j-w[i]]+c[i]})\) –- 二階背包問題
\(dp[i]=max(dp[i],dp[j]+1),\forall arr[i] > arr[j]\land i > j\) –- LIS 最長遞增子序列
\(dp[i][j]=\begin{cases}dp[i-1][j-1]+1,s[i]=t[j]\\max(dp[i-1][j],dp[i][j-1]),s[i]\ne t[j]\end{cases}\) –- LCS 最長共通子序列
題序 : 身上帶太多的零錢會很麻煩,因此會希望店員在找零錢能夠以最少的硬幣數來找,而不是全部都用1元塞給我們。
也就是要用最少的硬幣數湊出目標數字,具體作法為比較「每個硬幣的面額」與「其次小硬幣的面額」
假設需要找$86
【情況1】硬幣有:$50, $10, $5, $1 四種面額,由於每個數字都是次小數字的倍數,因此可以直接用greedy寫掉,從最大的硬幣去選。答案為 50*1 + 10*3 + 5*1 + 1*1 總共六枚
【情況2】硬幣有:$50, $46, $10, $5, $1 五種面額,這時會發現greedy好像怪怪的,因此這時候就需要使用 [ 動態規劃 ] 去完成這題。
\(dp[ x ]\):紀錄目前要湊成金額 \(x\) 的最少硬幣數目。
測試每個硬幣面額\(coins[ i ]\)
狀態轉移方程:當採用一個新的硬幣面額可以使用更少的硬幣數目來湊成金額 j 時,更新 dp[
\(j\) ] = min( dp[
\(j\) ], dp[
\(j\) – coins[
\(i\) ]] + 1)
時間複雜度 : 找錢的範圍\(N\),零錢種類數量\(M\),總共有\(NM\)個問題,因此時間複雜度為\(O(NM)\)
n 個物品儘量塞進背包裡面,令背包裡面的物品總價值最高。背包有重量限制,如果物品太重,就會撐破背包。
這就是廣為人知的背包問題,其有許多變形,而本堂課將介紹最經典的 [ 0/1 背包問題 ] 「 0/1 」的意思是:每種物品只會放進背包零個或一個。一個物品要嘛整個不放進背包、要嘛整個放進背包。物品無法切割。
看到這種問題若沒學過直覺通常會是貪心,不管是貪心他的價值或是貪心他的CP值也好,在這種題目下面都是錯的。
0/1 背包問題的關鍵點,在於如何有效利用背包的剩餘重量,找出最好的物品組合方式。
第一步,分割問題。然而分割問題的方式很簡單:對某一件物品來說,我們可以選擇放或不放;然後移去這件物品,縮小問題範疇。
一件物品不放進背包,背包價值不變、背包耐重不變;一件物品放進背包,背包價值上升、背包耐重下降。遞迴公式為:
\(c\) (\(n\), \(w\)) \(=\) \(max\)\(( c(n-1, w)\), \(c(n-1, w-weight[n])\) \(+\) \(cost[n]\) )
就可以依照這個遞迴公式去設計top-down的版本,而bottom-up的迴圈版本如下:
for (int i = 0; i < n; ++i)
for (int j = w; j - weight[i] >= 0; j--) // 由後往前
dp[j] = max(dp[j], dp[j - weight[i]] + cost[i]);
\(dp[ x ]\):紀錄目前背包重量限制為 \(x\) 的可裝最大價值。
測試每個物品\(weight[ i ]\)
狀態轉移方程:當有一個更好的方法是在同重量下可以獲得更高價值時,更新 \(dp[j] = max(dp[j], dp[j - weight[i]] + cost[i]);\)
初始化 : \(dp[ i ] = 0\)
時間複雜度 : 背包的範圍\(N\),物品種類數量\(M\),總共有 \(NM\) 個問題,因此時間複雜度為 \(O(NM)\)
題序 : 從一連串的整數序列中選出最長的嚴格遞增子序列(strictly longest increasing subsequence)。例如:在 \(1, 3, 2, 2, 4, 0\) 中最長的嚴格遞增子序列為 \(1, 3, 4\) 或者 \(1, 2, 4\)。
第一步 分割問題,會發現有許多遞增子序列都是符合要求的子序列,因此解法只需要記錄在每個長度下最長的遞增子序列長度
第二步 設計算法,每次檢查當前的是否比前一個大,若是 則 dp 式轉移+1
範例代碼
int LIS(){
// 初始化。每一個數字本身就是長度為一的 LIS。
for (int i=0; i<N; i++) length[i] = 1;
for (int i=0; i<N; i++)
// 找出 s[i] 能接在哪些數字後面,
// 若是可以接,長度就增加。
for (int j=0; j<i; j++)
if (s[j] < s[i])
length[i] = max(length[i], length[j] + 1);
// length[] 之中最大的值即為 LIS 的長度。
int l = 0;
for (int i=0; i<N; i++)
l = max(l, length[i]);
return l;
}
\(dp[ i ]\) : 以\(s[i]\)為結尾的最長遞增子序列長度
測試每個字串結尾\(s[ i ]\)
狀態轉移方程:當有一個更好的方法是在同長度下可以獲得更長序列時,更新 : \(dp[i]=max(dp[i],dp[j]+1)\)
初始化:\(dp[i]=1, (1 \le i \le n)\) 至少選自己長度為1
時間複雜度 : 狀態數\(O(N)\),轉移複雜度\(O(N)\),共有\(N*N\)個問題,所以總複雜度\(O(N^2)\)
題序 : 給定兩個字串\(s, t\),求 \(s\) 與 \(t\) 的最長共同子序列( Longest Common Subsequence )
第一步 分割問題,會發現有許多共同子序列都是符合要求的子序列,因此解法只需要開兩個維度記錄在每個分別前綴下的最長共同子序列長度
第二步 設計算法,每次檢查當前的是否與另一個的當下一樣,若是一樣 則
\(dp[ i ][ j ] = dp[ i-1 ][ j-1 ] + 1\)
否則 \(dp[ i ][ j ]\) 就會等於 \(dp[i-1][j]\) 或 \(dp[ i ][ j-1 ]\)
x = "ABCBDAB"
y = "BDCABA"
要尋找哪一個才是合法的LCS時,我們就需要紀錄每一個字符的選取,由於每次查找的是 \(dp[x-1][y]\) 跟 \(dp[x][y-1]\) 那個長度更長。最後從 \(len1\) , \(len2\) 开始往前回溯,輸出最常公共子序列。
範例代碼
void output(int x,int y){
if(!x&&!y)
return ;
if(tag[x][y]==0){
output(x-1,y-1);
cout<<s1[x-1];
}
else if(tag[x][y]==1)
output(x-1,y);
else
output(x,y-1);
}
int main(){
while (cin >> s1 >> s2) {
l1 = strlen(s1);
l2 = strlen(s2);
for(int i=1;i<=l1;i++)
tag[i][0]=1;
for(int i=1;i<=l2;i++)
tag[0][i]=-1;
for (int i=1; i<=l1; i++) {
for (int j=1; j<=l2; j++) {
if (s1[i-1] == s2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
tag[i][j] = 0;
}
else if(dp[i-1][j]>=dp[i][j-1]){
dp[i][j] = dp[i-1][j];
tag[i][j] = 1;
}
else{
dp[i][j]=dp[i][j-1];
tag[i][j] = -1;
}
}
}
cout << dp[l1][l2] << "\n";
output(l1,l2);
}
}
\(dp[i][j]\)代表字串前綴\(s_{0...i}\)與\(t_{0...j}\)的LCS
轉移式 : \(dp[i][j]=\begin{cases}dp[i-1][j-1]+1,s[i]=t[j]\\max(dp[i-1][j],dp[i][j-1]),s[i]\ne t[j]\end{cases}\)
初始化 : \(dp[i][1]=dp[1][j]=0\)
時間複雜度 : 狀態數\(O(n^2)\),轉移複雜度\(O(1)\),總複雜度\(O(n^2)\)
通常為了方便會把 \(dp\) 陣列平移,且此 DP 可以滾動
滾動數組的作用在於優化空間。因為DP題目是一個自底向上的擴展過程,我們常常需要用到的是線性的解,前面的解往往不用紀錄。所以用滾動數組優化是很有效的。利用滾動數組的話在N很大的情況下可以達到壓縮存儲的作用,通常可以直接壓掉一個維度的大小。
ex: dp[N][M] \(\to\) dp[N]
int cur,pre=1,ppre=0;
for(int i=2;i<=n;i++)
cur=pre+ppre,ppre=pre,pre=cur;
一個\(n\times n\)方格棋盤,從左上角走到右下角,每次只能往右走一格或者往下走一格。請問有幾種走法?
example :
第一步 分割問題 會發現對於任何一個方格來說,只可能「從上走來」或者「從左走來」,答案是兩者相加,也就是說可以從上方以及左方的方格步數推算出當前這格的步數。
設計轉移式 \(dp[i][j]\)代表走到當前 \(i\), \(j\) 格有幾種方法,因此\(dp[i][j] = dp[i-1][j] + dp[i][j-1]\)
然後這時候就會發現,他的轉移式只需要用到\(i\)的前一項或者是\(j\)的前一項,那是否可以節省空間呢
答案是必然的,如果不需要儲存所有問題的答案,只想要得到其中一個特定問題的答案,那只需要一維陣列就夠了,也就是 O(N) 空間。
for (int i=1; i<N; i++)
for (int j=1; j<N; j++)
f[j] += f[j-1];
就成功的作出了空間優化了
DP是個博大精深的演算法,初學者剛學演算法很快就會碰到,然而難的DP也可以到變成防破台 也是因為DP不論從難度、類型來看,變化都非常多,所以幾乎所有競賽 DP 都扮演很重要的角色(台灣站更是每年 DP 占了都 1/3 的題數),也因此好好學會DP非常的重要!
DP不算是一個制式的演算法,而是一種概念,因此它的用途/形式多變想學好它不是很容易,要能在在看到題目時有辦法快速辨別能不能 DP/怎麼 DP 等只能靠多看題目多練習(把各種類型的DP都看很多次自然而然就會熟悉模式了(O))
–- Jakao
DP雖然有著需要通靈,通靈比賽等臭名,不過若你有著很清晰的思路可以分析每一個階段的話,其實DP不是一個需要那麼害怕的算法。
需要記得的就是在最一剛開始給你們舉例的步驟
也有人可以幾乎沒練習多少題就可以DP很強,那些通靈系選手就不太需要理他們