---
# System prepended metadata

title: '演算法課程題解 - 動態規劃\: 最長共同子序列 LCS'
tags: [SCIST 演算法 題解]

---

# 演算法課程題解 - 動態規劃\: 最長共同子序列 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 演算法 題解`