# Dynamic Programming
## Intro
把原問題分解成小問題，之後再求解
有點像數學的遞迴式
步驟:
1. 定義 $dp$ 的每一項代表什麼
2. 寫出初始狀態，例如 $dp[0] = 1$
3. 針對 $dp[i]$ 找出他的答案轉移來源
4. 寫出遞迴式(一般叫做轉移式或 $dp$ 式)
5. 寫
具體可以看底下的
多寫就熟了
## c095: 費氏數列
[**c095: 費氏數列**](https://judge.tcirc.tw/ShowProblem?problemid=c095)
1. 定義 $dp[i]$ 為費氏數列的第 $i$ 項
2. 寫出初始狀態，$dp[1] = 1,\ dp[2]=1$
3. $dp[i]$ 的轉移來源: $dp[i-1],\ dp[i-2]$
4. 寫出轉移式 $dp[i] = dp[i-1]+dp[i-2]$
5. 寫
```cpp=
int n;
cin >> n;
vector<long long> dp(n + 10);
dp[1] = 1;
dp[2] = 1;
for (int i = 3; i <= n; i++)
{
dp[i] = dp[i - 1] + dp[i - 2];
}
cout << dp[n] << endl;
```
## 小朋友上樓梯最小成本
[**小朋友上樓梯最小成本**](https://judge.tcirc.tw/ShowProblem?problemid=d066)
1. 定義 $dp[i]$ 為走到第 $i$ 階的最小成本
2. 寫出初始狀態，$dp[0] = 0$
3. $dp[i]$ 的轉移來源: 如果要走到第 $i$ 階，上一步一定是在第 $i-1$ 或 $i-2$ 階，所以轉移來源是 $dp[i-1],\ dp[i-2]$
4. 寫出轉移式: 因為題目要求最小成本，所以選 $dp[i-1],\ dp[i-2]$ 比較小的那個，再加上自己這階的成本就得到走到第 $i$ 階的最小成本。轉移式: $dp[i] = min(dp[i-1],\ dp[i-2])+cost[i]$
5. 寫
```cpp=
int main()
{
int n;
cin >> n;
vector<int> v(n);
for (int i = 0; i < n; i++)
{
cin >> v[i];
}
vector<int> dp(n);
dp[0] = v[0];
dp[1] = v[1]; // 沒辦法走兩階到達第一階
for (int i = 2; i < n; i++)
{
dp[i] = min(dp[i - 1], dp[i - 2]) + v[i];
}
cout << dp[n - 1] << endl;
}
```
## d069: P-6-6. 方格棋盤路線
[**d069: P-6-6. 方格棋盤路線**](https://judge.tcirc.tw/ShowProblem?problemid=d069)
因為要走到 $(i,\ j)$ 一定是從 $(i-1,\ j)$ 或 $(i,\ j-1)$ 來
定義 $dp[i][j]$ 為**走到 $(i,\ j)$ 時的最大得分**
則有轉移式
$dp[i][j]=\max(dp[i-1][j],\ dp[i][j-1])+value[i][j]$
答案為 $dp[m-1][n-1]$
跟小朋友上樓梯很像
:::warning
注意邊界!!!
:::
## C - Vacation
[**C - Vacation**](https://atcoder.jp/contests/dp/tasks/dp_c)
如果這回合要游泳，則上個回合只能抓蟲或寫功課
定義 $dp[i][j]$ 為第 $j$ 回合做第 $i$ 種動作的最大快樂度
$0,\ 1,\ 2$ 代表 $A,\ B,\ C$
則有轉移式
$dp[0][j]=\max(dp[1][j-1],\ dp[2][j-1])+a[j]$
$dp[1][j]=\max(dp[0][j-1],\ dp[2][j-1])+b[j]$
$dp[2][j]=\max(dp[0][j-1],\ dp[1][j-1])+c[j]$
而最後的答案會是 $\max(dp[0][n],\ dp[1][n],\ dp[2][n])$
```cpp=
long long n;
cin >> n;
vector<long long> a(n), b(n), c(n);
vector<vector<long long>> dp(3, vector<long long>(n));
for (int i = 0; i < n; i++)
{
cin >> a[i] >> b[i] >> c[i];
}
dp[0][0] = a[0];
dp[1][0] = b[0];
dp[2][0] = c[0];
for (int i = 1; i < n; i++)
{
dp[0][i] = max(dp[1][i - 1], dp[2][i - 1]) + a[i];
dp[1][i] = max(dp[0][i - 1], dp[2][i - 1]) + b[i];
dp[2][i] = max(dp[0][i - 1], dp[1][i - 1]) + c[i];
}
cout << max({dp[0][n - 1], dp[1][n - 1], dp[2][n - 1]}) << endl;
// 3 個以上的數字取 min/max
```
## d052: P-4-13. 最大連續子陣列 (同 P-5-2)
[**d052: P-4-13. 最大連續子陣列 (同 P-5-2)**](https://judge.tcirc.tw/ShowProblem?problemid=d052)
定義 $dp[i]$ 是以 $a[i]$ 結尾的最大連續子陣列
要嘛接在前一項後面，要嘛自己當新的頭
所以可以寫出轉移式
$dp[i] = \max (dp[i-1]+a[i],\ a[i])=\max (dp[i-1],\ 0)+a[i]$
最後答案是 $dp$ 中的最大值
## D - Index × A(Not Continuous ver.)
[**D - Index × A(Not Continuous ver.)**](https://atcoder.jp/contests/abc267/tasks/abc267_d)
定義 $dp[i][j]$ 為 **選第 $j$ 個，且他的權重為 $i$ 時的最大值**
被選的上一項一定在第 $j$ 個之前，而且他的權重一定是 $i-1$
所以 $dp[i][j]$ 可能的轉移來源為 $dp[i-1][0]$ 到 $dp[i-1][j-1]$
則有轉移式
$dp[i][j]=\max\limits_{0\leq k<j}(dp[i-1][k])+v[j]\times i$
而 $\max$ 可以邊 $dp$ 邊算
:::info
:::spoiler 怎麼算
有一個陣列 $mx$，$mx[j]:=\max\limits_{0\leq k\leq j}(dp[i-1][k])$
就可以寫出轉移式
$mx[j]=max(mx[j-1],\ dp[i-1][j])$
:::
最後答案是 $\max\limits_{1\leq i \leq n}(dp[m][i])$
```cpp=
long long n, m;
cin >> n >> m;
vector<long long> v(n);
for (int i = 0; i < n; i++)
{
cin >> v[i];
}
vector<vector<long long>> dp(m, vector<long long>(n, -1e18));
for (int i = 0; i < n; i++)
dp[0][i] = v[i];
for (int i = 1; i < m; i++)
{
long long mx = dp[i - 1][i - 1];
for (int j = i; j < n; j++)
{
dp[i][j] = mx + v[j] * (i + 1); // 0-based dp
mx = max(dp[i - 1][j], mx);
}
}
long long mx = dp[m - 1][m - 1];
for (int i = m; i < n; i++)
{
mx = max(dp[m - 1][i], mx);
}
cout << mx << endl;
```
## 經典題:背包問題
### 0-1 背包
題目大意:有一個能裝總重 $w$ 的背包和 $m$ 種商品，每種商品都有一個價值和重量，
問這個背包的最大價值?
當然並不總是重量和價值，例如 [**這題**](https://judge.tcirc.tw/ShowProblem?problemid=b054) 和 [**這題**](https://cses.fi/problemset/task/1158)
總之概念都差不多
:arrow_down: 為了方便說明，以下面這題為例
**[D - Knapsack 1](https://atcoder.jp/contests/dp/tasks/dp_d)**
$n$ 個物品，背包最大載重為 $w$
定義 $dp[i][j]$ 為**選前 $i$ 個物品，背包最大載重為 $j$ 時的最大價值**
從第一個物品跑到最後一個
對於第 $i$ 個物品
不拿: $$dp[i][j]=dp[i-1][j]\ \ \ \forall j\in[0,\ w]$$
拿: $$dp[i][j]=(dp[i-1][j-weight[i]])+value[i]\ \ \ \forall j\in[weight[i],\ w]$$
對 **拿/不拿** 兩種情況取最大值
最後答案為 $dp[n][w]$
:::info
因為 $j$ 越大， $dp[i][j]$ 就越大 (大背包能裝更多東西)
所以可以直接用 $dp[i-1][j-weight[i]]$
:::
code:
```cpp=
int n, w;
cin >> n >> w;
vector<int> weight(n + 1), value(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> weight[i] >> value[i];
}
int dp[n + 1][w + 1] = {};
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= w; j++)
{
if (j - weight[i] >= 0)
{
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
else
{
dp[i][j] = dp[i - 1][j];
}
}
}
cout << dp[n][w] << endl;
```
時間複雜度為 $\mathcal{O}(nw)$
空間複雜度為 $\mathcal{O}(nw)$
#### 優化 (滾動)
注意到轉移來源只有**上一輪的 $dp$**
其他部分都沒用
所以可以改成只開兩個陣列，一個是現在的，一個是上一輪的
做完之後把這輪的變成上一輪，一直做下去
時間複雜度為 $\mathcal{O}(nw)$
空間複雜度為 $\mathcal{O}(w)$
code:
```cpp=
long long n, w;
cin >> n >> w;
vector<long long> weight(n), value(n);
for (int i = 0; i < n; i++)
{
cin >> weight[i] >> value[i];
}
long long dp1[w + 1] = {}, dp2[w + 1] = {};
for (int i = 0; i < n; i++)
{
for (int j = 0; j <= w; j++)
{
if (j - weight[i] >= 0)
{
dp2[j] = max(dp1[j], dp1[j - weight[i]] + value[i]);
}
}
for (int j = 0; j <= w; j++)
{
dp1[j] = dp2[j];
}
}
cout << dp1[w] << endl;
```
<br>
又注意到轉移來源總是在自己左方
所以可以**由後往前做**
這樣只需要開一個一維陣列
時間複雜度為 $\mathcal{O}(nw)$
空間複雜度為 $\mathcal{O}(w)$
code:
```cpp=
long long n, w;
cin >> n >> w;
vector<long long> weight(n), value(n);
for (int i = 0; i < n; i++)
{
cin >> weight[i] >> value[i];
}
long long dp[w + 1] = {};
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]] + value[i]);
}
}
cout << dp[w] << endl;
```
### 變體:有限背包
**[Book Shop II](https://cses.fi/problemset/task/1159)**
跟剛剛一樣，只是每種東西可以重複選
如果把所有物品拆成一個一個的話時間複雜度為 $\mathcal{O}(x \times \Sigma k_i)=\mathcal{O}(x\times n\times k)$
顯然不會過
所以把每個 $k_i$ 拆成 $1,\ 2,\ 4,\ 8...$ 個一組
這樣就可以 $dp$ 了
時間複雜度為 $\mathcal{O}(x\times \Sigma\log k_i)=\mathcal{O}(x\times n\times \log k)$
## d070: P-6-7. LCS
[**d070: P-6-7. LCS**](https://judge.tcirc.tw/ShowProblem?problemid=d070)
**LCS (Longest common subsequence)**
兩字串的最長共同子序列
子序列 : 某個序列的子序列是從最初序列通過去除某些元素但不破壞餘下元素的相對位置（在前或在後）而形成的新序列。
```
a: "algorithm"
b: "alignment"
LCS(a, b): "algm" or "algt"
```
定義 $dp[i][j]$ 為 $a[0,\ i]$ 和 $b[0,\ j]$ 的 **LCS** 長度
如果 $a[i]=b[j]$ :
$$dp[i][j]=dp[i-1][j-1]+1$$
如果 $a[i]\neq b[j]$ :
$$dp[i][j]=\max(dp[i-1][j],\ dp[i][j-1])$$
<br>
$$
code:
```cpp=
string a, b;
cin >> a >> b;
int n = a.length(), m = b.length();
int dp[m + 1][n + 1] = {};
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
if (a[j - 1] == b[i - 1]) // 0-based string
{
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else
{
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
cout << dp[m][n] << endl;
```
## 題目
**[c081: A.Town traveler](https://judge.tcirc.tw/ShowProblem?problemid=c081)
[c082: B.傳統弓箭與六藝禮射](https://judge.tcirc.tw/ShowProblem?problemid=c082)
[H - Grid 1](https://atcoder.jp/contests/dp/tasks/dp_h)
[d072: Q-6-4. 闖關二選一](https://judge.tcirc.tw/ShowProblem?problemid=d072)
[d085: Q-6-14. K 次買賣 (106 高中全國賽 subtask)](https://judge.tcirc.tw/ShowProblem?problemid=d085)
[c090: 大獅子和樓梯](https://judge.tcirc.tw/ShowProblem?problemid=c090)
[Edit Distance](https://cses.fi/problemset/task/1639/)**
[**Atcoder Educational DP Contest**](https://atcoder.jp/contests/dp)
有 26 題 $dp$ ，據說寫完之後考化學都會及格(?)
[**DP on CSES**](https://cses.fi/problemset/list/)
有 19 題 $dp$ ，都是滿經典的題型
[**DP on CodeForces**](https://codeforces.com/problemset?tags=dp)
有數以百計的 $dp$ ，有些甚至不需要 $dp$
[**DP on TCIRC (AP325)**](https://judge.tcirc.tw/Problems?tag=DP)
是中文的，而且 AP325 不刷嗎?
Sign in with Wallet
Connect another wallet