---
# System prepended metadata

title: Dynamic Programming
tags: [' report', 109_FDCS]

---

---
tags: 109_FDCS, report
---
<!--
## 複習

快速冪code
```cpp=
constexpr int mod = 998244353;
long long pow(long long a, long long b){
    long long ret = 1;
    for(; /*...<1>...*/; b = /*...<2>...*/, a = /*...<3>...*/)
        if(/*...<4>...*/)
            ret = /*...<5>...*/;
    return ret;
}
```

:::spoiler <1>
`b`
:::

:::spoiler <2>
`b >> 1`
:::

:::spoiler <3>
`a * a % mod`
:::

:::spoiler <4>
`b & 1`
:::

:::spoiler <5>
`ret * a % mod`
:::
-->


# Dynamic Programming

- 空間換時間
<!--動態規劃在尋找有很多重疊子問題的情況的最佳解時有效。它將問題重新組合成子問題。為了避免多次解決這些子問題，它們的結果都逐漸被計算並被儲存，從簡單的問題直到整個問題都被解決。因此，動態規劃儲存遞迴時的結果，因而不會在解決同樣的問題時花費時間。-->
- 由部分最佳解推出整體最佳解
<!--動態規劃只能應用於有最佳子結構的問題。最佳子結構的意思是局部最佳解能決定全域最佳解（對有些問題這個要求並不能完全滿足，故有時需要引入一定的近似）。簡單地說，問題能夠分解成子問題來解決。-->


## fibonacci sequence

#### 遞迴

最直覺的解法

```cpp=
long long fib(int x) {
	if (x < 2) return x;
	return fib(x - 1) + fib(x - 2);
}
```
時間複雜度$O(\phi^n)$

### 轉移式

{$$dp_i=\begin{cases}i&i<2\\dp_{i-1}+dp_{i-2}&otherwise\end{cases}$$}

#### DP解

將答案存起來避免重複計算

```cpp=
long long ans[100];
long long fib(int x) {
	if (x < 2) return x;
	return ans[x] ? ans[x] : (ans[x] = fib(x - 1) + fib(x - 2));
}
```
時間複雜度$O(n)$, 空間複雜度$O(n)$

#### 滾動DP

```cpp=
long long fib(int x) {
	vector<int> v{0, 1};
	for (int i = 2; i <= x; i++)
		v[i & 1] += v[~i & 1];
	return v[x & 1];
}
```

時間複雜度$O(n)$, 空間複雜度$O(1)$

### 例題

[a069: I Love You 3000](http://203.64.191.163/ShowProblem?problemid=a069)
[a244: pD Minecraft 1.15 嗡嗡蜂群更新 上線啦!!!!](http://203.64.191.163/ShowProblem?problemid=a244)
[a372: 又來爬樓梯](http://203.64.191.163/ShowProblem?problemid=a372)

---

## Longest Common Subsequence(LCS)

### 轉移式

{$$dp_{i,j}=\begin{cases}1+dp_{i-1,j-1}&a_i=b_j\\max(dp_{i-1,j},dp_{i,j-1})&otherwise\end{cases}$$}

#### DP解

```cpp=
vector<vector<int>> dp(a.size() + 1, vector<int>(b.size() + 1));
for (size_t i = 0; i < a.size(); i++)
	for (size_t j = 0; j < b.size(); j++) {
		if (a[i] == b[j]) dp[i + 1][j + 1] = 1 + dp[i][j];
		else dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
	}
cout << dp[a.size()][b.size()] << endl;
```

時間複雜度$O(nm)$, 空間複雜度$O(nm)$

#### 滾動DP

```cpp=
auto& a = max(inputa, inputb, [](auto& x, auto& y) {return x.size() < y.size();});
auto& b = min(inputa, inputb, [](auto& x, auto& y) {return x.size() < y.size();});
vector<vector<int>> dp(2, vector<int>(b.size() + 1));
for (size_t i = 0; i < a.size(); i++)
	for (size_t j = 0; j < b.size(); j++) {
		if (a[i] == b[j]) dp[~i & 1][j + 1] = 1 + dp[i & 1][j];
		else dp[~i & 1][j + 1] = max(dp[i & 1][j + 1], dp[~i & 1][j]);
	}
cout << dp[a.size() & 1][b.size()] << endl;
```

時間複雜度$O(nm)$, 空間複雜度$O(min(n,m))$
### 例題
[c001: 10405 - Longest Common Subsequence](https://zerojudge.tw/ShowProblem?problemid=c001)

---

## 路徑總數

### 轉移式

{$$dp_{i,j}=\begin{cases}1&i=1\ or\ j=1\\dp_{i-1,j}+dp_{i,j-1}&otherwise\end{cases}$$}

#### DP解

```cpp=
vector<vector<int>> dp(n, vector<int>(m, 1));
for (int i = 1; i < n; i++)
	for (int j = 1; j < m; j++)
		dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod;
cout << dp.back().back() << endl;
```

時間複雜度$O(nm)$, 空間複雜度$O(nm)$

#### 滾動DP

```cpp=
auto n = max(a, b);
auto m = min(a, b);
vector<vector<int>> dp(2, vector<int>(m, 1));
for (int i = 1; i < n; i++)
	for (int j = 1; j < m; j++)
		dp[i & 1][j] = dp[~i & 1][j] + dp[i & 1][j - 1];
cout << dp[~n & 1].back() << endl;
```

時間複雜度$O(nm)$, 空間複雜度$O(min(n,m))$

### 例題

[d198: 00825 - Walking on the Safe Side](https://zerojudge.tw/ShowProblem?problemid=d198)
[d378: 最小路徑](https://zerojudge.tw/ShowProblem?problemid=d378)

---

## 其他DP

## [a227: B.B.K.K.B.K.K.](http://203.64.191.163/ShowProblem?problemid=a227)

### 轉移式

{$$dp_i=\begin{cases}2&i=1\\6&i=2\\2\times (dp_{i-1}+dp_{i-2})&otherwise\end{cases}$$}

#### DP解

```cpp=
vector<int> v{1, 2, 6};
for (int i = 3; i <= n; i++)
	v[i % 3] = (v[(i - 1) % 3] + v[(i - 2) % 3]) << 1;
cout << v[n % 3] << endl;
```

時間複雜度$O(n)$, 空間複雜度$O(1)$

### 例題
[c878: 107北二5.議會質詢紀錄](https://zerojudge.tw/ShowProblem?problemid=c878)

---

## 樹上DP

這不會考 :poop:

### 例題

[20200704 APCS P4](/@emanlaicepsa/APCS202007?fbclid=IwAR0t4NRoIV4fBzrmpEXxCj535AgkUx9l90hrZ9GjMrOTXg-WtuR2OKZYkbI#p4)


:::spoiler 範例code
```cpp=
//沒在OJ上試過，可能有些小bug
#include<iostream>
#include<vector>
#include<functional>
using namespace std;
const string dic = "AUCG";
struct node {
	string val;
	vector<long long> ch, dp;
};
int main() {
	int n, m, a, b, root;
	cin >> n >> m;
	vector<node> v(n);
	for (int i = 0; i != n; i++) {
		cin >> a >> b >> v[a - 1].val;
		if (a == b) root = a - 1;
		else v[b - 1].ch.emplace_back(a - 1);
	}
	long long sum = 0;
	for (int k = 0; k != m; k++) {
		static function<void(int)> dfs = [&](int x) {
			v[x].dp.assign(4, 0);
			for (const auto& i : v[x].ch) dfs(i);
			for (int i = 0; i != 4; i++) {
				if (v[x].val[k] != '@' && v[x].val[k] != dic[i]) {
					v[x].dp[i] = 1e9; continue;
				}
				for (auto& j : v[x].ch) {
					long long minn = 1e9;
					for (int l = 0; l != 4; l++)
						minn = min(minn, v[j].dp[l] + (l != i));
					v[x].dp[i] += minn;
				}
			}
		};
		dfs(root), sum += min({v[root].dp[0], v[root].dp[1], v[root].dp[2], v[root].dp[3]});
	}
	cout << sum << endl;
	return 0;
}
```
:::
