# **CSES DP詳細解法**
**動機**:在考APCS的時候，我發現自己對動態規劃不了解、熟練度不足，因此常陷入無從下手、時間不夠的困境。為了加強我這方面的能力，我決定到cses練習刷題，並製作自己的詳解。雖然網路上已有其他人製作詳解，但我發現有些寫的比較簡潔，讓新手需花比較多時間理解，因此本詳解會注重在圖解部分，並詳細說明步驟。
**感謝**:謝謝tmting39的講義，Anthony Ngene的youtubequ頻道提供的解題方法及教學。以及台中一中資訊讀書會、電研提供的教學。
# 1.Dice Combination
[https://cses.fi/problemset/task/1633](https://)
:::spoiler 解法:
x的組合數會是x-1,x-2,...x-6加起來。以下圖為例:
可以得知4有以下共8種解法:
1+1+1+1/2+1+1/1+2+1/3+1/1+1+2/2+2/1+3/4
定義0有1種解法，那從1開始:
dp[1]=dp[0];
dp[2]=dp[0]+dp[1];
dp[3]=dp[0]+dp[1]+dp[2]
...
dp[8]=dp[2]+dp[3]+dp[4]+dp[5]+dp[6]+dp[7]
dp[x]=dp[x-6]+dp[x-5]....+dp[x-1]
另外要記住若x<6的話要注意不要減到變負數
|0|1|2|3|4|5|6|7|
|-|-|-|-|-|-|-|-|
|1|1|2|4|8|16|32|63|
```
程式碼施工中請稍候
```
:::
# 2.Minimizing Coins
[https://cses.fi/problemset/task/1634](https://)
:::spoiler 解法:
對於x來講，他的最少硬幣數dp[x]=min(dp[x-c1],dp[x-c2],dp[x-c3]....)+1
以11 {1,5,7}舉例
dp[0]=0
dp[1]=dp[1-1]+1
dp[2]=dp[2-1]+1
...
dp[5]=min(dp[5-1],dp[5-5])+1
|0|1|2|3|4|5|6|7|8|9|10|11|
|-|-|-|-|-|-|-|-|-|-|-|-
|0|1|2|3|4|1|2|1|2|3|2|3
```
程式碼施工中請稍候
```
:::
# 3.Coin Combinations I
[https://cses.fi/problemset/task/1635](https://)
:::spoiler 解法:
這題跟第一題差不多，只是第一題限定由1~6組成，而這題教你輸入硬幣，以8 {2,3,5}為例:
共有6種解法，分別是:
2+2+2+2/3+3+2/3+2+3/2+3+3/5+3/3+5
定義0有一種解法
dp[1]=0
dp[2]=dp[0]
dp[3]=dp[1]+dp[0]
...
dp[9]=dp[7]+dp[6]+dp[4]
dp[x]=dp[x-c1]+dp[x-c2]+dp[x-c3]...
一樣要小心邊界
|0|1|2|3|4|5|6|7|8|
|-|-|-|-|-|-|-|-|-
|1|0|1|1|1|3|2|5|6
```
程式碼施工中請稍候
```
:::
# 4.Coin Combinations II
https://cses.fi/problemset/task/1636
:::spoiler 解法:
這題跟上面1、3題不太一樣，由於加的順序不同不能重複算到，因此我們要分開討論，先從幣值最小的硬幣開始討論方法數，接者往下看，討論是否使用新硬幣。拿以下的dp表格做講解，以9,{2,3,5}為例:
| | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|-|-|-|-|-|-|-|-|-|-|-|
| 2 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 3 | 1 | 0 | 1 | 1 | 1 | 1 | 2 | 1 | 2 | 2 |
| 5 | 1 | 0 | 1 | 1 | 1 | 2 | 2 | 2 | 3 | 3 |
dp[i][j]=dp[i-1][j]「不使用新硬幣」+dp[i][j-c]「使用新硬幣」
舉例:dp[1][6]=dp[0][6]+dp[1][3]
分別有2+2+2/3+3兩種可能
dp[2][9]=dp[1][9]+dp[2][4]
分別有2+2+2+3/3+3+3/2+2+5三種可能
```
程式碼施工中請稍候
```
:::
# 5.Removing Digits
https://cses.fi/problemset/task/1637
:::spoiler 解法:
這題其實可以直接減，用python的字串處理方便很多
```
a=input()
b=0
while a!=0:
b=b+1
a=str(a)
a=list(a)
c=sorted(a)
c.reverse()
maxn=c[0]
a=''.join(a);
a=int(a)
a=a-int(maxn)
print(b)
```
另外c++解法未來補上
:::
# 6.Grid Paths
https://cses.fi/problemset/task/1638
:::spoiler 解法:
其實跟數學寫排列組合時遇到的那種題目差不多
dp[i][j]=dp[i-1][j]+dp[i][j-1]
trap的部分當作0
```
程式碼施工中
```
:::
# 7.Book Shop
https://cses.fi/problemset/task/1158
:::spoiler 解法:
就是經典的0/1背包問題，開dp表格討論當前物品要選擇還是丟棄，直接上表格當範例，以題目的測資來看
| | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|-|-|-|-|-|-|-|-|-|-|-|-|
| (3,1) | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| (4,5) | 0 | 0 | 0 | 1 | 5 | 5 | 5 | 6 | 6 | 6 | 6 |
| (5,8) | 0 | 0 | 0 | 1 | 5 | 8 | 8 | 8 | 9 | 13 | 13 |
| (8,12) | 0 | 0 | 0 | 1 | 5 | 8 | 8 | 8 | 12 | 13 | 13 |
dp[i][j]=max(dp[i-1][j] (不選這個，繼承上方的),dp[i-1][j-hi]+si(選這個，加上價值))
```
#include<iostream>
#include<utility>
#include<algorithm>
using namespace std;
int main()
int n;
int x;
cin>>n>>x;
pair<int,int> moneypage[n];
int total[n+1][x+1];
for(int k=0;k<n;k++){
cin>>moneypage[k].first;
}
for(int k=0;k<n;k++){
cin>>moneypage[k].second;
}
sort(moneypage,moneypage+n);
for(int i=0;i<n+1;i++){
for(int j=0;j<x+1;j++){
total[i][j]=0;
}
}
for(int i=1;i<n+1;i++){
for(int j=1;j<x+1;j++){
if(j-moneypage[i-1].first>=0){
total[i][j]=max(total[i-1][j],total[i-1][j-moneypage[i-1].first]+moneypage[i-1].second);
}else{
total[i][j]=total[i-1][j];
}
}
}
cout<<total[n][x];
```
:::
# 8.Array Description
https://cses.fi/problemset/task/1746
:::spoiler 解法:
直接開表格紀錄，以題中測資為例:
| | 2 | 0 | 2 |
|-|-|-|-|
| 1 | 0 | 1 | 2 |
| 2 | 1 | 1 | 3 |
| 3 | 0 | 1 | 2 |
| 4 | 0 | 0 | 1 |
| 5 | 0 | 0 | 0 |
dp[i][j]代表那一格的方法數，可以繼承給dp[i+1][j+1]、dp[i][j]
、dp[i-1][j]
記得注意邊界和取餘數
```
施工中
```
:::
# 9.Counting Towers
https://cses.fi/problemset/task/2413
:::spoiler 解法
對於每個2x1的格子，有兩種結果，中間有一條線的和沒有線的
而這兩種分別會衍伸處下列幾種
也就是說，中間沒線的會衍伸出兩種中間沒線的和一種中間有線的
中間有線的會衍伸出一種中間沒線的和四種中間有線的
若沒線是x，有線是y
x'=2x+y
y'=x+4y
```
程式碼施工中
```
:::
# 10.Edit Distance
https://cses.fi/problemset/task/1639
:::spoiler 解法:
這題和LCS蠻像的，但不太一樣。我們先開dp表格
dp[i][j]代表第一個字串長度i轉移到第二個字串長度j時所需要的步數。我們考慮三種可能的操作：
dp[i-1][j] + 1：刪除 A[i-1]（讓 A 縮短）
dp[i][j-1] + 1：插入 B[j-1]（等於在 A 加上這個字元）
dp[i-1][j-1] + 1：若 A[i-1] != B[j-1] 則替換
dp[i-1][j-1] 否則不需替換
:::
# 11.Rectangle Cutting
https://cses.fi/problemset/task/1744
:::spoiler 解法:
首先注意這題不能貪心 一開始的直覺可能會是直接長邊減短邊，但這樣會出事。舉例來說，500x499若直接切成499x499和1x499，會多切非常多刀。因此這題我們只能窮舉。
開一個dp表格，dp[i][j]代表i x j時的刀數。對於一個長方形，找出所有切割方式的最小值
:::
# 12.Money Sums
https://cses.fi/problemset/task/1745
:::spoiler 解法:
這題如果直接窮舉會TLE，因此要想辦法避免重複計算
方法是這樣，以題中測資{4,2,5,2}為例
開一個set一剛開始有{0}
接著每一個硬幣都加上去丟進set裡
4 {0,4}
2 {0,4,0+2,4+2}
5 {0,4,2,6,0+5,4+5,2+5,6+5}
2 {0,4,2,6,5,9,7,11,0+2,4+2,6+2,5+2,9+2,,7+2,11+2}
因為set裡不會重複而且自動排序，所以最後會剩
{0,2,4,5,6,7,8,9,11,13}
將0排除掉就可以輸出了
```
施工中
```
:::
# 13.Removal Game
https://cses.fi/problemset/task/1097
:::spoiler 解法:
開個dp表格，dp[i][j]代表陣列剩下第i項到第j項時，先手的人可獲得的最大值
當我們在 a[i...j] 中做選擇時，有兩個選項：
1.拿走a[i]，剩下的是a[i+1...j]，對手會拿那一段中他能拿到的最大值(也就是 dp[i+1][j]）
2.拿走a[j]，剩下的是a[i...j-1]，對手拿的是dp[i][j-1]
所以我們希望讓對手拿到的最小（因為剩下的就是我們的分數）：
dp[i][j]=sum(i,j)-min(dp[i+1][j],dp[i][j-1])
:::
# 14.Two Sets II
https://cses.fi/problemset/task/1093
:::spoiler 解法:
兩set內加起來相等，代表一個set內的值加起來是[(1+n)n/2]/2
接著就跟之前寫過的題目很像啦，給你硬幣，問目標數的組合有幾種。記得要除2，因為分成兩個set。
:::
# 15.Increasing Subsequence
https://cses.fi/problemset/task/1145
:::spoiler 解法:
這就是個標準的LIS(longest increasing subsequence)問題。
我們開一個vector紀錄目前的LIS，若當前數字比LIS的結尾還大，則可進入LIS，否則取代vector中大於等於此數的最小值(注意，由於這題只要求長度，固可如此操作)
舉例{7 3 5 3 6 2 9 8}
{7}
{3} 7是大於等於3的最小值，故取代
{3,5}5>3，故加上
{3,3}
{3,3,6}
{2,3,6}
{2,3,6,9}
{2,3,6,8}
實際上真正的LIS是{3,5,6,9}或{3,5,6,8}但長度是相同的
證明:我們只有在數字大於vector結尾時才會加入新數字，因此能維持至今為止的正確長度，而取代的意義是我們希望當前LIS的結尾越小越好，這樣我們能夠更容易加長LIS。
```
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n; // 讀入數列長度
int a[n]; // 原始數列
vector<int> temp; // 用來記錄 LIS 的中間狀態
for (int i = 0; i < n; i++) {
cin >> a[i]; // 讀入數列中的每個數字
}
temp.push_back(a[0]); // 初始化：把第一個數放進 temp
// 從第二個數開始處理
for (int i = 1; i < n; i++) {
if (a[i] > temp.back()) {
// 如果 a[i] 比目前 LIS 的最後一個數還大，表示可以延長 LIS
temp.push_back(a[i]);
} else {
// 否則，在 temp 中找第一個大於等於 a[i] 的數，將它取代為 a[i]
// 這樣可以保證相同長度的 LIS，其結尾數越小越好，方便未來延長
*lower_bound(temp.begin(), temp.end(), a[i]) = a[i];
}
}
// 輸出 LIS 的長度（temp 的大小就是最長遞增子序列長度）
cout << temp.size();
}
```
:::
# 16.Projects
https://cses.fi/problemset/task/1140
:::spoiler
這題我們要先將資料離散化，避免記憶體爆掉。接著我們知道一個project的結束時間越早越好，這樣我們能夠快點做新的任務。
因此我們要照結束時間排序。然後我們可以開一個一維dp陣列紀錄我們當前的最好得分。記住，project做完才有得分，所以我們在project做完之前只會繼承左邊分數。而當project做完了已後，我們看當前得分比較高(不做這個任務)，還是這個任務開頭的時間時的得分+這個任務的得分比較高。也就是dp[任務結束時間]=max(dp[任務結束時間(不選擇任務)],dp[任務開始時間]+任務得分)
:::
# 17.Elevator Rides
https://cses.fi/problemset/task/1653
:::spoiler 解法:
這題要用位元dp。我們把1當作挑這個物品，0當作不挑。例如0110就是挑第二和第三個東西。對於一個新的人，如果他塞得進目前的電梯，那電梯數就不用更新，並且更新當前電梯載重。如果塞不下，就開新的電梯。
那位元dp要如何窮舉呢?
四個人都進電梯，這個狀態能是由123人已在電梯，考慮第4人的狀態，又或者是124人在電梯，考慮第三人的狀態
註:這篇程式碼參考自https://hackmd.io/hTQrRJDaQ2C2X9UouWengw?view#%E4%BD%8D%E5%85%83dp
另外，解釋一下a<<b 的意思是a x 2^b
```
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, maxWeight;
cin >> n >> maxWeight; // 輸入人數與電梯最大承重
vector<int> weight(n); // 每個人的體重
for (int i = 0; i < n; i++) {
cin >> weight[i];
}
// dp[mask] 表示當前 （已上電梯的人組合）最少需要幾趟電梯
// last[mask] 表示目前這趟電梯上已經載的總重量
vector<int> dp(1 << n), last(1 << n);
dp[0] = 1; // 初始狀態：沒人搭乘，預設 1 趟空電梯
last[0] = 0; // 現在這趟電梯還沒載人
for (int mask = 1; mask < (1 << n); mask++) {
dp[mask] = INT_MAX;
last[mask] = INT_MAX;
for (int j = 0; j < n; j++) {
if (mask & (1 << j)) { // 如果第 j 個人在這個狀態中已經被安排搭電梯
int prevMask = mask ^ (1 << j); // 嘗試從未安排第 j 人的狀態轉移過來
// 嘗試把第 j 人放進當前這一趟電梯
if (last[prevMask] + weight[j] <= maxWeight) {
if (dp[prevMask] < dp[mask] || (dp[prevMask] == dp[mask] && last[prevMask] + weight[j] < last[mask])) {
dp[mask] = dp[prevMask];
last[mask] = last[prevMask] + weight[j];
}
} else {
// 超重了，需要另開一趟電梯給他
if (dp[prevMask] + 1 < dp[mask] || (dp[prevMask] + 1 == dp[mask] && weight[j] < last[mask])) {
dp[mask] = dp[prevMask] + 1;
last[mask] = weight[j]; // 新的那趟電梯只有這個人
}
}
}
}
}
cout << dp[(1 << n) - 1] << endl; // 所有人都上去時的最少電梯趟數
return 0;
}
```
:::
# 18.Counting Tilings
https://cses.fi/problemset/task/2181
:::spoiler 解法:
我們先看圖解
我們從第一欄開始，每一格可能是放橫的(占用右邊那格)，也可能是放直的(占用下面那格)。因為可能占用到第二欄，我們開一個bitmask紀錄方便我們轉移。我們把第一欄都填完後，就可以去看下一欄。塗黑的部分代表已經確定填完的，我們可以不用管他，接著塗第二欄，一樣有可能放左或放右。直到我們填到最後一欄，最後一欄只能填直的，不然會超出邊界。
註:程式碼參考至https://www.youtube.com/watch?v=byM079e5gmU ，大家也可以看他的影片圖解，促進理解
```
#include <bits/stdc++.h>
using namespace std;
// tilings[i][mask] 表示：已經填好前 i 欄，目前第 i 欄的狀態為 mask 的填法數
int tilings[1001][1 << 10]; // 最多 1000 欄、2^10 種 mask 狀態（因為 n ≤ 10）
int n, m;
const int MOD = 1e9 + 7; // 防止整數溢位，對結果取模
// 遞迴嘗試如何從 curr_mask 填到 next_mask
void fill_column(int column, int idx, int curr_mask, int next_mask) {
// 如果已經填完第 column 欄的所有 row（idx == n）
if (idx == n) {
// 將這種填法數量加到下一欄的 next_mask 狀態中
tilings[column + 1][next_mask] =
(tilings[column + 1][next_mask] + tilings[column][curr_mask]) % MOD;
return;
}
// 如果 curr_mask 的第 idx 位是 1，表示這個位置已經被填過
if (curr_mask & (1 << idx)) {
// 跳過這格，處理下一格
fill_column(column, idx + 1, curr_mask, next_mask);
} else {
// 嘗試在第 idx 列直放一個骨牌（往下一欄延伸）
fill_column(column, idx + 1, curr_mask, next_mask | (1 << idx));
// 嘗試橫放骨牌：需確保 idx + 1 也尚未填
if ((idx + 1 < n) && !(curr_mask & (1 << (idx + 1)))) {
// 橫放骨牌會佔據 idx 和 idx + 1，更新 next_mask 不需變
fill_column(column, idx + 2, curr_mask, next_mask);
}
}
}
int main() {
cin >> n >> m; // 讀入棋盤大小：n 行 m 列
tilings[0][0] = 1; // 初始狀態：第 0 欄為空，填法數為 1
// 從第 0 列處理到第 m-1 列
for (int column = 0; column < m; column++) {
// 遍歷當前欄的所有可能狀態
for (int mask = 0; mask < (1 << n); mask++) {
// 只有填法數大於 0 的狀態才需要進行遞迴轉移
if (tilings[column][mask] > 0) {
fill_column(column, 0, mask, 0); // 嘗試從當前 mask 生成下一欄的狀態
}
}
}
// 最後輸出填滿 m 列且最後一欄狀態為 0（全填滿）的方式總數
cout << tilings[m][0];
}
```
:::
# 19.Counting Numbers
https://cses.fi/problemset/task/2220
:::spoiler 解法:
這題若直接一個一個一個檢查會超時，因此我們要分開討論
0是1種
對於一個一位數，符合規則的有1~9 共9種
對於一個二位數，開頭不可以是0，而第二位可以是0~9但不能和第一位一樣，因此共有9x9種
同理可知，對於n位數，共有9的n次方種。
拿題目來看，我們可以把321拆成幾個部分:
0,1~9 ,10~99 ,100~299 ,300~319 ,320~321
所以最高位數減一(3-1)乘上後面位數的種數(9^2)，這裡是(100~299)。接著加上小於當前的位數(9x9+9+1)
接著看還沒討論完的，由於2小於3我們不用排除跟前面一樣的，可以直接加上2x9 (300~319 )，最後加上2(320~321)
由於題目是a和b之間的數，因此我們可以分別算出a-1的數和b的數再相減求出答案
這題額外要注意的是，求次方時不要使用<cmath> 裡的pow(i,j)。這個函式回傳的資料型態是double，而double超過一定位數(通常是15~17 )，會失去精準度，因此建議自己寫次方函式
```
施工中
```
:::
Sign in with Wallet
Connect another wallet