---
# System prepended metadata

title: DP

---

# DP
#  DP

DP(動態規劃)，把會重複用到的值存取下來讓在做運算的時候可以更加的快速

## 費氏數列

### 遞迴
```cpp
int fib(int n) {
    if(n <= 1) return 1;
    return fib(n - 1) + fib(n -  2);

}
```
複雜度 $O(\phi^N)$
可以觀察到，對於每一個$fib(N)$都需要重新算過一次，所以複雜度十分不友善

### DP解

```cpp
int N;
int dp[N + 1] = {0};
void fib(int n) {
    if(n == 0) {dp[0] = 1; return;}
    if(n == 1) {dp[1] = 1; return;}
    fib(n - 1); fib(n - 2);
    dp[n] = dp[n - 1] + dp[n - 2];
} 
```
也可以用for迴圈跑(速度較快)
```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(log N)$，以後會提到

## LIS最長遞增子序列

在解出$DP$之前第一步是要先列轉移式
{
$$    
  \begin{cases}
      dp[i] = max(dp[i], dp[j] + 1) \quad &if \;\;ar[i] > ar[j]\\
      dp[i] = max(dp[i], dp[j]) \quad &else
  \end{cases}    
$$
    
}
### DP 解
```cpp=
    int dp[N], ar[N];
    dp[0] = 1;
    for(int i = 1; i < N; i++)
        for(int j = 0; j < i; j++)
                dp[i] = max(dp[i], dp[j] + int(ar[i] > ar[j]));

    int mx = -1;
    for(auto &i : dp) mx = max(mx, i);  
```


時間複雜度$O(N^2)$
空間複雜度$O(N)$
### 二分搜解
時間複雜度
```cpp=
vector<int> dp;
int ar[N];
dp.emplace_back(int(1e9));
for(auto &i : ar) {
    if(i > dp.back()) dp.emplace_back(i);
    else  *lower_bound(dp.begin(), dp.end(), i) = i;
}
```
 時間複雜度$O(NlogN)$
 空間複雜度$O(N)$

最常遞增子序列也可以用$CDQ$分治去解，時間複雜度為$O(NlogN)$, 用$CDQ$解的優勢是可以快速地拓展到高維

## LCS最常共同子序列
給予兩個字串$S, T$，問他們的最常共同子序列為何

### 轉移式
{
$$
\begin{cases}
    dp[i][j] = dp[i-1]dp[j-1] + 1 \quad &if \;\; S[i] == T[j] \\
    dp[i][j] = max(dp[i-1][j], dp[j][i-1]) \quad &else
\end{cases}
$$
}

### dp解
```cpp=
string S, T;
const int S_len = S.size(), T_len = T.size();
int dp[S_len + 1][T_len + 1];
for(int i = 1; i <= S_len; i++) {
    for(int j = 1; j <= T_len; j++) {
        if(S[i] == T[j])
            dp[i][j] = dp[i-1][j-1] + 1;
        else
            dp[i][j] = max(dp[i-1][j], dp[j][i-1]);
    }
}
```

## 背包問題

### 0/1背包問題

$dp[i][k]$代表在再放第`i`個物品的時候，當背包容量為`k`可放的最大值
$w[i]$第`i`個物品的重輛
$val[i]$第`i`個物品的價值
{
$$
\begin{cases}
    dp[0][j] = 0\\
    dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + val[i])
\end{cases}
$$
}
就是對於每一個物品選擇要放或不放

然後要注意的是`j`在遞迴的時候要從$K$跑到$w[i]$，不然會重複取到 

```cpp=
int dp[N + 1][K + 1]; //有N個物品，背包容量為K
memset(dp[0], 0, sizeof(dp[0]));
for(int i = 1; i <= N; i++) {
    for(int j = K; j >= w[i]; j--) {
        dp[i][j] = max(dp[i-1][j] + dp[i-1][j-w[i]] + val[i]);
    }
}
```

### 滾動DP
可以發現到，每一次被取到的都會只有`dp[i-1]`，所以其實只要去紀錄前一列`dp`的值就可以了
```cpp=
int dp[2][K+1];
memset(dp[0], 0, sizeof(x));
for(int i = 1; i <= N; i++) {
    for(int j = K; j >= w[i]; j--) {
        dp[i&1][j] = max(dp[~i&1][j], dp[~i&1][j-w[i]] + val[i]);
    }
}
```

### 無限背包問題
就是一件物品可以放無限多件在背包裡
剛剛有說如果$j$不從$K$往下跑的話會重複取到，剛剛好符合無限背包的條件，所以只又把$j$改成從$w[i]跑到K就可以了$
```cpp=
int dp[2][K+1];
memset(dp[0], 0, sizeof(dp[0]));
for(int i = 1; i <= N; i++) {
    for(int j = w[i]; j <= K; j++) {
        dp[i&1][j] = max(dp[~i&1][j], dp[~i&1][j-w[i]] + val[i]);
    }
}
```


### 有限背包問題
那如果限定一個物品最多只能放$m$次呢，如果把它拆成**0/1背包**來做的話，時間複雜度會變成$O(mNK)$，顯然不太優秀，所以我們會把它拆成`2`的次方來去處理

時間複雜度$O(NKlogm)$
$cnt[i]為第i個物品可以放幾次$
```cpp=
int dp[2][K+1];
bool op = 1;
memset(dp[0], 0, sizeof(dp[0]));
for(int i = 1; i <= N; i++) {
    for(int j = 1; cnt[i] >= j;cnt[i] -= j, j <<= 1) {
       int weight = j * w[i], value = j * val[i];
       for(int k = K; k >= weight; k--) 
           dp[op][k] = max(dp[~op][k], dp[~op][k-weight] + value);
       op ^= 1;
    }  
    int weight = cnt[i] * w[i], value = cnt[i] * val[i];
    for(int k = K; k >= w[i]; k--) {
        dp[op][k] = max(dp[~op][k], dp[~op][k-weight] + value);
    }
    if(cnt[i]) op ^= 1;
}
````
有限背包問題也可以用單調對列壓成$O(NK)$，以後會提到

以上為基本的$DP$，接下來會進到更高深的$DP$

## 矩陣DP

簡單來說就是對於一些轉移是是用加或減，轉移是是固定取某些的$DP$，透過一定的規則來把轉移式換成矩陣，再利用`快速冪`來達到$O(log N)$級別的演算法

### 費氏數列
{
$$
\begin{cases}
    dp_0 = dp_1 = 1\\
    dp_n = dp_{n-1} + dp_{n-2} \quad n >=2
\end{cases}
$$
}

轉換成
{
$$
\left[
    \begin{array}{c}
        a_1 & a_0
    \end{array}
\right]
\times
\left[
    \begin{array}{cc}
        1 & 1 \\
        1 & 0
    \end{array}
\right] ^N
$$
}

```cpp=
struct matrix {
    V<V<int>> mat;
    
}
```

## 區間DP

就是用$DP$去維護一個區間的值，最經典的題目是給予$N$個矩陣，求將他們依序相乘所需花費的最小計算量

$dp[i][j]是第[i, j]中的矩陣相乘所需要話費的最小計算量$
$ar[i] 為第i個矩陣的大小 col \times row，$
{
$$
dp[i][j] =
\begin{cases}
    1 \quad &if \; i = j \\\\
    max(\\
    \quad dp[i+1][j] + (ar[i].col \times ar[i].row) \times ar[j].col), &else\\
    \quad dp[i][j-1] + (ar[i].col \times (ar[j].col * ar[j].row)\\
    ) 
\end{cases}
$$
}


## 狀態壓縮
有時候在做$DP$的時候，不只需要考慮一種狀態，可能同時會有許多種狀態，狀態壓縮就是把需要用到的狀態壓成以二進位來表示，如果有$N$個條件需要考慮($0$或$1$)，就會需要用到$2^N$個狀態

### 旅行售貨員問題

## 單調對列
對於特定的$DP$來說，他的答案可能會有$單調性$，也就是答案會是遞增的。
這時候就可以使用`單調對列`，就是在做$DP$的過程中，在維護最大值的情況下把不可能會用到的刪掉，大多都會用`deque`來去維護，可以達到$O(N)$的複雜度

## 斜率優化

雖然單調對列看起來已經十分的實用，但是對於一些後面的值會出現在前面的$dp$就不管用了，於是就出現了斜率優化，藉由對$dp$式子進行一些數學的簡化，來讓我們可以更好的去解決他

### 凸包

即給予多個點，招出一個凸多邊形他的頂點解由給予的點組成，且裡面包含所有的點

### 李超線段樹




## 自己出題目