# LIS&LCS

# LIS
$LIS$全名$Longest\ Increasing\ Subsequence$
也就是最常遞增子序列
顧名思義，最長遞增的子序列
在一個的序列中，找到一個子序列，使得這個子序列元素為遞增，且這個子序列的長度為最大。

## DP解法
狀態
$dp[i]為a[i]$以為結尾的最長遞增子序列的長度(a為數列)
轉移式
$dp[i] = max(dp[i], max(dp[j]) + 1) ,if\ j\ <\ i\ and\ a[j]\ <\ a[i]$
時間複雜度$O(n^2)$

例子
3 4 6 5 1 3 7
dp[1] = 1 (LIS為3)
dp[2] = 2 (LIS為3 4)
dp[3] = 3 (LIS為3 4 6)
dp[4] = 3 (LIS為3 4 5)
dp[5] = 1 (LIS為1)
dp[6] = 2 (LIS為1 3)
dp[7] = 4 (LIS為3 4 5 7 or 3 4 6 7)
所以LIS長度為4

## 實作範例

#include<bits/stdc++.h>
using namespace std;

int main(){ios::sync_with_stdio(0);cin.tie(0);
	int n;
	cin >> n;
	vector<int> a(n);
	for(int i = 0; i < n; i++){
		cin >> a[i];
	}
	vector<int> dp(n);
	fill(dp.begin(),dp.end(),1);
	for(int i = 0; i < n; i++){
		for(int j = 0; j < i; j++){
			if(a[j] < a[i]){
				dp[i] = max(dp[j] + 1, dp[i]);
			}
		}
	}
	int ans = 0;
	for(int i = 0; i < n; i++){
		ans = max(ans,dp[i]);
	}
	cout << ans << '\n';
}

## 二分搜解法
當LIS[back] < a[i]：代表a[i]能接在LIS[back]後面增加長度
否則，找到 LIS中第一個大於等於a[i]的元素然後把這個元素替換成a[i]
因為a[i]替換後能在後面接更多元素

這個方法陣列中的數有可能不是正確的LIS(很有可能不是)
但長度會是對的

時機複雜度$O(nlogn)$
## 實作

int main()
{
    int n;
    while (cin >> n)
    {
        vector<int> v;
        for (int i = 0, x; i < n; i++)
        {
            cin >> x;
            if (!v.size() || x > v.back())
                v.push_back(x);
            else
                *lower_bound(v.begin(), v.end(), x) = x;
        }
        cout << v.size() << '\n';
    }
}

# LCS
$LCS$全名$Longest\ Common\
Subsequence$
最常共同子序列

## 解法
這題我們可以先考慮兩個字串的最後一個字元，並將問題分成四種狀況
假設現有兩個字串A B長度都是10，並組成一個二維陣列LCS代表不同子字串下LCS的長度
1. 如果最後兩字串的最後一個字元一樣，那LCS就是兩個字串分別去調最後一個字元的LCS
LCS[9][9] = LCS[8][8] + 1
2. 如果最後兩個字串的最後一個字元只有一個字是包含在最佳解的
LCS[9][9] = LCS[9][8] or LCS[8][9]

根據以上2點可以發現，每格LCS都是由其上方、左方、左上方更新而來的
遞迴式:
$LCS[i][j]=$
$\{max(LCS[i-1][j], LCS[i][j-1])\ \ ,A[i] != B[j]$
$\{LCS[i-1][j-1] + 1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ,A[i] == B[j]$
示意圖:
> 圖片來自下方演算法筆記，裡面有動畫模擬過程
> https://web.ntnu.edu.tw/~algo/Subsequence2.html

時間複雜度O(NM)

## 實作

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main(){
	string s1, s2;
	cin >> s1 >> s2;
	int n = s1.size();
	int m = s2.size();
	int dp[n+1][m+1];
	for(int i = 0; i <= n; i++){
		dp[i][0] = 0;
	}
	for(int i = 0; i <= m; i++){
		dp[0][i] = 0;
	}
	for(int i = 1; i <= m; i++){
		for(int j = 1; j <= n; j++){
			if(s1[j-1] == s2[i-1]){
				dp[j][i] = dp[j-1][i-1] + 1;
			}
			else{
				dp[j][i] = max(dp[j-1][i], dp[j][i-1]);
			}
		}
	}
	cout << dp[n][m] << '\n';
}

### 滾動DP

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main(){
	string s1, s2;
	cin >> s1 >> s2;
	int n = s1.size();
	int m = s2.size();
	int dp[n+1][2];
	for(int i = 0; i <= n; i++){
		dp[i][0] = 0;
		dp[i][1] = 0;
	}
	int from = 0, to = 1;
	for(int i = 1; i <= m; i++){
		for(int j = 1; j <= n; j++){
			if(s1[j-1] == s2[i-1]){
				dp[j][to] = dp[j-1][from] + 1;
			}
			else{
				dp[j][to] = max(dp[j-1][to], dp[j][from]);
			}
		}
		swap(from, to);
	}
	cout << dp[n][from] << '\n';
}