# 演算法課程題解 - 動態規劃\: 最長共同子序列 LCS # UVa 10405 ## 題目 http://domen111.github.io/UVa-Easy-Viewer/?10405 給兩個字串，求兩字串的最長共同子序列 ## 想法 By Koios 從兩個字串的最後面一個字看回來，如果兩個字是相同的，那麼把它包含在子序列當中必定是最好的，因為再取前面的字串，子字串的長度必定是 $\leq$ 取當前這個的總長度。 那麼如果兩個字是不同的，那麼有兩種選擇 1. 留下第一個字串的 2. 留下第二個字串的 所以，當我們決定好要**取**或是**不取**某些元素之後，剩下的就是同類型的子問題了 根據上面的觀察可以得出 DP 式 定義 $dp[i][j]$ 表示第一個字串的前 $i$ 個字元以及第二個字串的前 $j$ 個字元組成的 LCS 最大長度 令第一個字串為 $s$ ，第二個字串為 $t$ 則有轉移式 $$ \begin{cases} dp[i][j] = dp[i-1][j-1] + 1 \quad \quad s[i] == t[j] \\ dp[i][j] = max(dp[i-1][j], dp[i][j-1]) \end{cases} $$ :::info ***Tips*** 如果刻意地讓 dp 式的 $i, j$ 都由 $1$ 開始的話，我們就不需要額外判斷邊界問題了~ ::: :::warning 題目的字串是可以包含空格的 ::: ### 程式碼 ```cpp= //By Koios1143 #include<iostream> using namespace std; int dp[1005][1005]; string s, t; int main(){ while(getline(cin, s) && getline(cin, t)){ for(int i=1 ; i<=s.size() ; i++){ for(int j=1 ; j<=t.size() ; j++){ if(s[i-1] == t[j-1]) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]); } } cout<<dp[s.size()][t.size()]<<"\n"; } return 0; } ``` ### 時間複雜度分析 DP 每個狀態轉移時間複雜度為 $O(1)$ 總共有 $|t||s|$ 個狀態，DP 總時間複雜度為 $O(|t||s|)$ 每筆測資總時間複雜度為 $O(|t||s|)$ # UVa 111 ## 題目 http://domen111.github.io/UVa-Easy-Viewer/?111 在歷史考試當中學生被要求要對歷史事件作排序，給分的方式為 - 每個在最長（但不一定要連續）的序列事件中，其相對的順序亦可以在標準答案發現者，每個事件得1分 也就是說，如果我們能在學生回答的順序當中找到一串最長的子序列，使得子序列當中的所有事件在正確答案當中的相對順序相同，那麼這些答案都得 1 分 現在告訴你正解以及學生回答的**每個事件發生的順序**，請依序回答每個學生的得分。 ## 想法 By Koios 題目其實等同要我們求正解以及學生答案的**最長共同子序列** 那麼，一樣從兩個序列的最後一個元素看回來 如果最後的元素相同，那麼加進子序列當中必定會是最好的。 如果最後的元素不同，那麼有兩種選擇 1. 留下第一個序列的元素 2. 留下第二個序列的元素 所以，當我們決定好要**取**或是**不取**某些元素之後，剩下的就是同類型的子問題了 根據上面的觀察可以得出 DP 式 定義 $dp[i][j]$ 表示第一個序列前 $i$ 個元素以及第二個序列前 $j$ 個元素的 LCS 長度 假設第一個序列為 $A$，第二個序列為 $B$ 則有轉移式 $$ \begin{cases} dp[i][j] = dp[i-1][j-1] + 1 \quad \quad A[i] == B[j] \\ dp[i][j] = max(dp[i-1][j], dp[i][j-1]) \end{cases} $$ :::info ***Tips*** 如果刻意地讓 dp 式的 $i, j$ 都由 $1$ 開始的話，我們就不需要額外判斷邊界問題了~ ::: :::warning 題目給的是**每個事件發生的順序**，而不是直接依照事件的發生順序輸入 所以記得預先將序列對應成**每個順序對應到哪個事件** ::: ### 程式碼 ```cpp= //By Koios1143 #include<iostream> using namespace std; int n, tmp, ans_ary[25], stu_ary[25], dp[25][25]; int main(){ while(cin>>n){ // 記得要對應好 for(int i=1 ; i<=n ; i++){ cin>>tmp; ans_ary[tmp] = i; } while(cin>>tmp){ stu_ary[tmp] = 1; for(int i=2 ; i<=n ; i++){ cin>>tmp; stu_ary[tmp] = i; } for(int i=1 ; i<=n ; i++){ for(int j=1 ; j<=n ; j++){ if(ans_ary[i] == stu_ary[j]) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]); } } cout<<dp[n][n]<<"\n"; } } return 0; } ``` ### 時間複雜度分析 每筆測資輸入時間複雜度為 $O(N)$ DP 每個狀態轉移時間複雜度為 $O(1)$ 總共有 $N^2$ 個狀態，DP 總時間複雜度為 $O(n^2)$ 每筆詢問總時間複雜度為 $O(n + n^2)$ # TOJ 26 ## 題目 https://toj.tfcis.org/oj/pro/26/ 給一個字串，求最長回文子字串的長度為何 也就是說移除最少的字元，使得字串變成回文字串，求該回文字串的長度 ## 想法 By Koios 回文的定義是前後對應的字元都相同 所以現在我們可以假想有兩個箭頭分別指向字串的頭跟尾 如果說兩個箭頭指到的字元相同，那麼包含進回文一定可以使回文總長度最長 如果兩個箭頭指到的字元不同，那麼我們可以選擇移除後面指向的字元，抑或是選擇刪除前面指項的字元 這樣觀察過後，發現到跟過去寫 LCS 的題目觀察點是相同的 換個角度再看一次這個題目 現在我們有字串 $s$ 以及把 $s$ 翻轉過來的字串 $s'$ 題目其實就等同於求 $LCS(s, s')$ 剛剛分別指向前端以及後端的指標分別指向 $s$ 以及 $s'$ 的前端 發現到其實是一樣的概念 那麼就回到 LCS 的 DP 部分 定義 $dp[i][j]$ 表示第一個字串前 $i$ 個字元以及第二個字串前 $j$ 個字元的 LCS 長度 則有轉移式 $$ \begin{cases} dp[i][j] = dp[i-1][j-1] + 1 \quad \quad s[i] == s'[j] \\ dp[i][j] = max(dp[i-1][j], dp[i][j-1]) \end{cases} $$ :::info ***Tips*** 如果刻意地讓 dp 式的 $i, j$ 都由 $1$ 開始的話，我們就不需要額外判斷邊界問題了~ ::: ### 程式碼 ```cpp= //By Koios1143 #include<iostream> using namespace std; int T, dp[3005][3005]; string s, t; int main(){ cin>>T; while(T--){ cin>>s; t = s; for(int i=0, j=s.size()-1 ; i<s.size() ; i++, j--){ t[j] = s[i]; } for(int i=1 ; i<=s.size() ; i++){ for(int j=1 ; j<=t.size() ; j++){ if(s[i-1] == t[j-1]) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]); } } cout<<dp[s.size()][t.size()]<<"\n"; } return 0; } ``` ### 時間複雜度分析 DP 每個狀態轉移時間複雜度為 $O(1)$ 總共有 $|s|^2$ 個狀態，DP 總時間複雜度為 $O(|s|^2)$ 每筆測資總時間複雜度為 $O(|s|^2)$ ###### tags: `SCIST 演算法 題解`