--- 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)) // 多維陣列都一樣`