# 1143. Longest Common Subsequence
##### link: https://leetcode.com/problems/longest-common-subsequence/
###### tags: `dp` `LCS`
* 這是 DP 問題中經典的 " 子序列問題 "
* 我們需要製作一個二維 DP 表，如下圖:

> 
>
此 DP 表的定義是：**對於字串 $str1[0...i-1]$ 和 $str2[0...j-1]$，他們的 LCS 長度是 $dp[i][j]$**

在更新 $dp$ 表時，要注意以下兩種情形：
1. $str1[i] == str2[j]$ ：$dp[i][j] = dp[i-1][j-1]+1$，因為是 $str1[i-1]$ 和 $str2[j-1]$ 所有的共同序列加上一個新來的 $str1[i]$ 字母。
2. $str1[i]$ != $str2[j]$：$dp[i][j] = max(dp[i-1][j], dp[i][j-1])$，因為 $str1[i]$ 和 $str2[j]$ 兩個字元至少有一個不在共同子序列中

* code：

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m=text1.size(), n=text2.size();
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        for (int i=1;i<=m;i++){
            for (int j=1;j<=n;j++){
                if (text1[i-1] == text2[j-1]){
                    dp[i][j] = dp[i-1][j-1]+1;
                }
                else if (text1[i-1] != text2[j-1]){
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[m][n];
    }
};

---
### 同場加映：d231. 97北縣賽-2-基因序列密碼問題
##### link: https://zerojudge.tw/ShowProblem?problemid=d231
* 概念一樣，只是這題要求印出共同子序列長什麼樣子。

#include <iostream>
#include <vector>

using namespace std;

string s1,s2;

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    while (cin>>s1>>s2){
        vector<vector<string>> dp(s1.size()+1,vector<string>(s2.size()+1,""));
        for (int i=1;i<=s1.size();i++){
            for (int j=1;j<=s2.size();j++){
                if (s1[i-1] == s2[j-1]){
                    dp[i][j] = dp[i-1][j-1]+ s1[i-1];
                }
                else if (s1[i-1] != s2[j-1]){
                    if (dp[i-1][j].size() > dp[i][j-1].size()) dp[i][j] = dp[i-1][j];
                    else dp[i][j] = dp[i][j-1];
                }
            }
        }
        if (dp[s1.size()][s2.size()] == "") cout<<"E"<<"\n";
        else cout<<dp[s1.size()][s2.size()]<<"\n";
        
    }

    return 0;
}