---
# System prepended metadata

title: DP 動態規劃
tags: [進階班]

---

---
tags: 進階班
---

# DP 動態規劃

## 主要觀念
- 把大問題拆分成小問題
- 把會算到很多遍的儲存下來

<!-- 
我把題目大概補了上來
有些不知道怎麼解釋:poop:
-->


## 費氏數列

### 遞迴解
```cpp= 
int fib(int n) {
    if(n == 1 || n == 0) return 1;
    else return fib(n - 1) +　fib(n - 2);
}
```

**<center>遞迴的過程</center>**

```graphviz
digraph main{
    f_0[label = "fib(0)"]
    f_1[label = "fib(1)"]
    f_1_1[label = "fib(1)"]
    f_2[label = "fib(2)"]
    
    "fib(4)" -> {"fib(3)", "fib(2)"}
    "fib(3)" -> {f_2, f_1_1}
    "f_2" -> {f_0, f_1}
    "fib(2)" -> {"fib(0)", "fib(1)"}
}
```


**時間複雜度$O(\phi^n)$**

---

### DP解


可以用一個陣列來記錄`fib(n)`的值，如果有重複算到的就直接回傳即可。

```cpp=
const int mxN = 10//n 最大的值

int dp[mxN]; //dp(大小, 初始值)
dp[0] = dp[1] = 1;

int fib(int n) {
    if(dp[n]) return dp[n];
    else return dp[n] = fib(n - 1) + fib(n - 2); //先把dp[n]附值再傳回
}
```    


時間複雜度$O(N)$ 
空間複雜度$O(N)$
也可以用迴圈解

```cpp=
int dp[n + 1];
dp[0] = dp[1] = 1;

for(int i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
}
```

時間複雜度$O(N)$
空間複雜度$O(N)$

實際複雜度會因題目不同而不同

---


## 路徑總數


### DP 解
```cpp= 
vector<vector<int>> dp(N + 1, vector<int>(M + 1, 0));
dp[0][1] = 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];
    }
}

```
時間複雜度$O(NM)$
空間複雜度$O(NM)$

空間複雜度似乎不太妙，可不可以縮減一下?

---

### 滾動DP解

```cpp=
vector<int> dp(M + 1, 0);
dp[1] = 1;
for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= M; j++) {
        dp[j] += dp[j - 1];
    }
}
cout << dp[M] << '\n';
```
時間複雜度$O(NM)$
空間複雜度$O(M)\; or \; O(min(M, N))$ 

---
## LCS(最長共同子序列)
<!-- 我不知道怎麼解釋-->
子序列定義：在一個字串中，去除 $\geq 0$ 個字元但不破壞其他字元的相對位置，此新字串即為原字串之子字串。

例：$fdcs$ 的子字串有：$\{\phi, f, d, c, s, fd, fc, fs, dc, ds, cs, fdc, fds, fcs, dcs, fdcs\}$

最長共同子字串：$n$ 個字串共有且長度最長的子字串 (以本例來看，$n = 2$)

### 轉移式
{$$dp_{ij} = \begin{cases}dp_{i-1,j-1} + 1 \quad &if& a_i = b_j \\ max(dp_{i-1, j}, dp_{i, j - 1})\quad &else\end{cases}$$}



### DP解
```cpp=
vector<vector<int>> dp(a.size() + 1, vector<int>(b.size() + 1, 0));

for(int i = 1; i <= a.size(); i++) {
    for(int j = 1; j <= b.size(); j++) {
        if(a[i] == b[j]) 
            dp[i][j] = dp[i -1][j - 1] + 1;
        else 
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    }
}
```
**a的長為N,    b的長為M**
時間複雜度$O(NM)$
空間複雜度$O(NM)$

### 滾動DP
```cpp=
vector<vector<int>> dp(2, vector<int>(b.size() + 1, 0));

for(int i = 1; i <= a.size() ;i++) {
    for(int j = 1;j <= b.size() ;j++) {
        if(a[i] == b[j]) 
            dp[i&1][j] = dp[~i&1][j - 1] + 1;
        else 
            dp[i&1][j] = max(dp[~i&1][j], dp[i&1][j-1]);
    }
}

```
**a的長為N,    b的長為M**
時間複雜度$O(NM)$
空間複雜度$O(M)$



---

## 背包問題

來看到`DP`的一個經典例題，背包問題。
#### 問題簡述
給予一個容量為`k`的背包。
和一些物品，每個物品都有其大小和價值。
問再不超過背包容量的條件下，能裝入的最大價值。

### 0/1背包
每項物品都只有一個

背包容量為`M`,有`N`個物品。
$v[i] \implies 第i個物品的價值$
$w[i] \implies 第i個物品的重量$

#### 轉移式
{
$$dp[i][j] = \begin{cases}dp[i-1][j]\quad &if\ j<  w[i]\\max(dp[i-1][j],v[i] +dp[i-1][j-w[i]])&else\end{cases}$$
}
#### DP解
```cpp= 
vector<int> v(N), w(N);
vector<vector<int>> dp(N, vector<int>(M + 1, 0));

for(int i = 0; i <　N; i++) {
    for(int j = 0; j < w[i]; j++) 
        dp[i][j] = dp[i - 1][j];
    for(int j = w[i]; j <= M; j++)
        dp[i][j] = max(dp[i - 1][j], v[i] + dp[i - 1][j - w[i]]);
}
```

時間複雜度$O(NM)$ 
空間複雜度$O(NM)$

#### 滾動DP

```cpp=
vector<int> v(N), w(N);
vector<int> dp(M + 1, 0);

for(int i = 0; i < N ;i++) {
    for(int j = M; j >= w[i]; j--)
        dp[j] = max(dp[j], v[i] + dp[j - w[i]]);
}
```

時間複雜度$O(NM)$ 
空間複雜度$O(M)$

:::info
Q: 為什麼要從後往前DP呢?
:::


### 無限背包

從前往後`DP`, 即可。
```cpp=
vector<int> v(N), w(N);
vector<int> dp(M + 1, 0);

for(int i = 0; i < N ;i++) {
    for(int j = w[i]; j <= M; j++)
        dp[j] = max(dp[j], v[i] + dp[j - w[i]]);
}
```
時間複雜度$O(NM)$
空間複雜度$O(M)$



---

### 有限背包
`DP,位元運算`

#### 一開始的想法
把每一個物品都做一次`O/1背包`。

```cpp=
vector<int> v(N), w(N), k(N);
vector<int> dp(M + 1, 0);
for(int i = 0; i < N;i ++) 
    for(int t = 0; t < k[i]; t++) 
        for(int j = M; j >= w[i]; j--) 
            dp[j] = max(dp[j], v[i] +　dp[j - w[i]])；
```

時間複雜度$O(kMN)$
空間複雜度$O(M)$
#### 嘗試優化
把物品的數量拆成二的倍數。
```cpp= 
vector<int> v(N), w(N), k(N);
for(int i = 0; i < N; i++) {
    int rest = k[i];
    int weight, val;
    
    for(int t = 1; t <= rest; t <<= 1) { //t *= 2
        rest -= t;        
        weight = t * w[i], val = t * val[i];
        
        for(int j = M;j >= weight; j--)
            dp[j] = max(dp[j], val + dp[j - weight]);
    }
    
    
    weight = t * w[i], val = t * v[i];
    
    for(int j = M; j >=; j++) {
        dp[j] = max(dp[j], val + dp[j - weight]);
    }
}
```

時間複雜度$O(NM\log k)$ 
空間複雜度$O(M)$





---
## 補充

### [無限階梯](http://203.64.191.163/ShowProblem?problemid=a650)
費氏數列的延伸
可以前進`K`和不前進，就是從前`K`格和當前格的方法相加。

:::spoiler code
```cpp=
const int mod = 1e9 +7;
int N, M;
	cin >> N >> M;
	V<V<int>> dp(2, V<int> (N, 0));
	dp[1][0] = 1; //dp[~0&1][0] = 1;
	for(int i = 0, a; i < M; i++) {
		cin >> a;
		for(int j = 0; j < N; j++) {
			int cur_pos = (j + a) % N;
			dp[i&1][cur_pos] = (dp[~i&1][cur_pos] + dp[~i&1][j]);
			dp[i&1][cur_pos] %= mod;
		}
		for(auto &j : dp[i&1]) cout << j << ' '; cout << endl;
	}
	cout << dp[~M&1][0] - 1<< endl;

```
:::

---
## 小結
`DP`的題目很多變，就多練題目，然後通靈:poop:

#### 補充：陣列的初始化

`memset(arr, 0, sizeof(arr)) // 多維陣列都一樣`
