# 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$式子進行一些數學的簡化，來讓我們可以更好的去解決他 ### 凸包 即給予多個點，招出一個凸多邊形他的頂點解由給予的點組成，且裡面包含所有的點 ### 李超線段樹 ## 自己出題目