# DP (2) ## 5/3 社課 ---- ## Outline - LCS - LIS - 背包問題 --- ## 名詞定義 **子序列** （subsequence） 從序列中取一些值出來而不改變其相對位置 **子字串／子陣列** （substring/subarray） 子序列取出的值在原序列中連續 ---- $\{1, 2, 3, 4, 5, 6\}$ $\{2, 3, 4\}$ 是子序列也是子陣列 $\{1, 5, 6\}$ 是子序列不是子陣列 $\{2, 5, 4\}$ 不是子序列不是子陣列 --- # LCS ---- ### [最長共同子序列](https://zerojudge.tw/ShowProblem?problemid=c001) **（Longest Common Subsequence, LCS）** 給定兩長度分別為 $n, m$ 的字串 $s, t$ 請輸出最長共同子序列長度 $n, m\le 3000$ ---- ### DP 三步驟 - 設定狀態 - 列出轉移式 - 定好邊界 ---- ### 設定狀態 假設 $dp[i][j]$ 為 $s(1\sim i)$ 和 $t(1\sim j)$ 的最長共同子序列長度 ---- ### 列出轉移式 如果 $s[i]=t[j]$ $\begin{multline*} dp[i][j]=\max(dp[i-1][j-1]+1, \\dp[i-1][j], dp[i][j-1]) \end{multline*}$ 如果 $s[i]\not=t[j]$ $dp[i][j]=\max(dp[i-1][j], dp[i][j-1])$ ---- 等等 真的要比那麼多東西嗎 ---- 如果 $s[i]=t[j]$ $\begin{multline*} dp[i][j]=\max(dp[i-1][j-1]+1, \\dp[i-1][j], dp[i][j-1]) \end{multline*}$ 注意到 $dp[i-1][j]$ 和 $dp[i][j-1]$ 與 $dp[i-1][j-1]$ 的差值一定不超過 $1$ 所以 $dp[i-1][j], dp[i][j-1]$ 會小於等於 $dp[i-1][j-1]+1$ 即 $dp[i][j]=dp[i-1][j-1]+1$ ---- ### 整理一下 如果 $s[i]=t[j]$ $dp[i][j]=dp[i-1][j-1]+1$ 如果 $s[i]\not=t[j]$ $dp[i][j]=\max(dp[i-1][j], dp[i][j-1])$ $O(nm)$ 完成轉移 ---- ### 定好邊界 字串沒有長度就不會有 LCS 產生 $dp[0][0]=0$ $dp[i][0]=dp[0][j]=0$ ---- ### 現在換[這題](https://atcoder.jp/contests/dp/tasks/dp_f) 同樣是 LCS 不過這次要求的是**子序列本身** 任意一個 LCS 都可以 ---- 我們可以記錄每個 $dp[i][j]$ 的來源 然後從最後面倒回去 ---- 具體一點 紀錄是怎麼來的 如果 $s[i]=t[j]$，設 $pre[i][j]=0$ 否則若 $dp[i-1][j]>dp[i][j-1]$，設 $pre[i][j]=1$ 否則設 $pre[i][j]=2$ ---- 接下來從後往前，用雙指針 ```cpp int i=n, j=m; string ans=""; while(i&&j){ if(!pre[i][j]) ans+=s[i], i--, j--; // 回去轉移來源 else if(pre[i][j]==1) i--; // 回去轉移來源 else j--; // 回去轉移來源 } reverse(ans.begin(), ans.end()); ``` ---- 這種作法稱作 DP 回溯 以記錄**最佳轉移來源**實作 --- # LIS ---- ### [最長（嚴格）遞增子序列](https://cses.fi/problemset/task/1145) **（Longest Increasing Subsequence, LIS）** 給定一長度 $n$ 的序列 $a$ 請輸出最長嚴格遞增子序列長度 $n\le 2\times10^5$ ---- 一樣先定個狀態 $dp[i]$ 表示以第 $i$ 項結尾的 LIS 長度 ---- 轉移 $dp[i]=\displaystyle\max_{j<i\land a_j<a_i}{\{dp[j]\}}+1$ 對於每個 $i$ 都要往前遍歷全部找最大值 $O(n^2)$ 太慢了 ---- 怎麼辦 單點修改，區間詢問最大值 開一棵線段樹嗎 好像太麻煩了 ---- 我們想求的是 在 $i$ 之前比 $a_i$ 小的某數其 $dp$ 值 那我們就維護每一種長度 IS 的最小結尾 ---- 可以開一個 `vector` $t$ 用來存每一種長度 IS 的最小結尾 令長度 $k$ 的 IS 其最小結尾為 $t_k$ 現在問題就變成找到最大的 $k$，滿足 $t_k<a_i$ ---- 怎麼找呢 注意到 $t$ 一定是嚴格遞增的 也就是具有單調性 因此我們可以二分搜！ 找到最大的 $k$ 後把 $t_{k+1}$ 更新成 $a_i$ 如果 $a_i$ 比 $t$ 的最後一項大，就把他加入結尾 最後 $t$ 的長度就會是答案 ---- $O(n\log{n})$ ```cpp= vector<int> t; // 存每種長度 IS 的最小結尾 for(int i=0; i<n; i++){ if(t.empty()||t.back()<a[i]) t.push_back(a[i]); // 前面的 IS 結尾比 a[i] 小 else t[lower_bound(t.begin(), t.end(), a[i])-t.begin()]=a[i]; // 二分搜 } int ans=t.size(); ``` ---- 最後 $t$ 所存的是每種長度 IS 的最小結尾 並不是真正的 LIS 如果要求 LIS 也可以用記錄轉移點的方式 各位可以自己試試看 ---- LIS 可以也可以有一些變形 像是從遞增變遞減 從嚴格變非嚴格 --- ## 背包問題 ---- ### [0/1 背包](https://atcoder.jp/contests/dp/tasks/dp_d) 有 $N$ 種物品 第 $i$ 種物品具有大小 $w_i$ 和價值 $v_i$，並且只有一個 現在有一個容量為 $W$ 的背包 即背包內大小總和不能超過 $W$ 則放進背包的物品價值總和最大是多少 $1\le N\le100, 1\le W\le 10^5$ $1\le w_i\le W, 1\le v_i\le 10^9$ ---- ### 設定狀態 $dp[i][j]$ 代表只看前 $i$ 種物品 大小總和是 $j$ 的最大總價值 ---- ### 列出轉移式 當我們看到第 $i$ 種物品，大小總和為 $j$ 時 可以選擇放或不放 放：$dp[i][j]=dp[i-1][j-w_i]$ 不放：$dp[i][j]=dp[i-1][j]$ 合併一下就是 $dp[i][j]=\max(dp[i-1][j-w_i], dp[i-1][j])$ ---- ### 定好邊界 $dp[0][0]=0$ 剩下的都設為 $-\infty$ 轉移的時候可以只取到存在的狀態 ---- 答案就是 $\displaystyle\max_{0\le j\le W}{\{dp[N][j]\}}$ ---- **$O(NW)$ 程式碼** ```cpp= #include<bits/stdc++.h> #define fastio ios::sync_with_stdio(0); cin.tie(0); using namespace std; typedef long long ll; int n, m; ll dp[105][100005], w[105], v[105]; int main(){ fastio cin >> n >> m; for(int i=1; i<=n; i++) cin >> w[i] >> v[i]; for(int i=1; i<=n; i++){ for(int j=0; j<=m; j++){ if(j<w[i]){ // 當前重量沒辦法取第 i 項 dp[i][j]=dp[i-1][j]; continue; } dp[i][j]=max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]); } } ll mx=0; for(int i=0; i<=m; i++) mx=max(mx, dp[n][i]); cout << mx << '\n'; } ``` ---- ### 無限背包 有 $N$ 種物品 第 $i$ 種物品具有大小 $w_i$ 和價值 $v_i$，並且有**無限個** 現在有一個容量為 $W$ 的背包 即背包內大小總和不能超過 $W$ 則放進背包的物品價值總和最大是多少 $1\le N\le100, 1\le W\le 10^5$ $1\le w_i\le W, 1\le v_i\le 10^9$ ---- 狀態和剛剛是一樣的 不過轉移的部分從 在這個重量下**要不要拿這個** 變成**要不要多拿一個** 因此轉移式變成 $dp[i][j]=\max(dp[i][j-w[i]], dp[i-1][j])$ ---- ### [CSES Coin Combinations I](https://cses.fi/problemset/task/1635) 有 $n$ 種硬幣 第 $i$ 種硬幣價值 $c_i$ 元，有無限多個 求有多少種方法可以湊到剛好 $x$ 元 ---- 把他轉換成類似背包問題 $dp[i][j]$ 代表看到第 $i$ 項，價值為 $j$ 的方法數 類似無限背包，有兩種轉移來源 所以 $dp[i][j]=dp[i][j-w_i]+dp[i-1][j]$ 答案就是 $dp[n][x]$ ---- 背包問題可以有很多變形 可以先把問題轉化成類似背包問題的敘述 再去考慮轉移問題 ---- ### 補充：有限背包 有 $N$ 種物品 第 $i$ 種物品具有大小 $w_i$ 和價值 $v_i$，並且有 $c_i$ 個 現在有一個容量為 $W$ 的背包 即背包內大小總和不能超過 $W$ 則放進背包的物品價值總和最大是多少 $1\le N\le100, 1\le W\le 10^5$ $1\le w_i, v_i, c_i\le 10^5$ ---- 先考慮分堆，把 $c_i$ 個都看成不同種物品 接著就是 0/1 背包 $O(W\sum{c_i})$ ---- 接著可以考慮有效一點的分堆方法 想想每種數字都可以分解為二進位 所以可以枚舉二進位裡的每個 bit 我們可以用 $k$ 個 bit 湊出 $[0, 2^k-1]$ 找到最大的 $k$ 使得 $2^k-1<=m$ 再多加上一個 $c_i-(2^k-1)$ 就可以湊出 $c_i$ 內的所有數 ---- 每個 $c_i$ 可以用 $\log{c_i}$ 的時間求出 總時間 $O(W\sum{\log{c_i}})$