最长公共子序列（LCS）

问题

---

给定两个字符串 s1 和 s2 ，求出一个最长的序列，使得该序列既是 s1 的子序列，也是 s2 的子序列。

样例

---

输入：
s1 = "ABC", s2 = "ACD"
输出：
2 ("AC")

输入：
s1 = "AGGTAB", s2 = "GXTXAYB"  
输出：
4 ("GTAB")

解法

---

设dp[i][j]为s1[0, i - 1]和s2[0, j - 1]的最长公共子序列的长度。
对于字符s1[i - 1]和字符s2[j - 1]，

• 如果s1[i - 1] == s2[j - 1]：
  说明当前字符可以作为s1[0, i - 1]和s2[0, j - 1]的最长公共子序列的一部分。
  则有：$dp[i][j]=dp[i-1][j-1]+1$
• 如果s1[i - 1] != s2[j - 1]：
  那么s1[0, i - 1]和s2[0, j - 1]的最长公共子序列会出现在下面三种情况中：
  1. s1[0, i - 1]和s2[0, j - 1]的最长公共子序列与s1[0, i - 2]和s2[0, j - 1]的最长公共子序列相同（s1[i - 1]无贡献）。
  2. s1[0, i - 1]和s2[0, j - 1]的最长公共子序列与s1[0, i - 1]和s2[0, j - 2]的最长公共子序列相同（s1[i - 1]无贡献）。
  3. s1[0, i - 1]和s2[0, j - 1]的最长公共子序列与s1[0, i - 2]和s2[0, j - 2]的最长公共子序列相同（s1[i - 1]和s2[j - 1]均无贡献）。
     而dp[i - 1][j]和dp[i][j - 1]一定大于等于dp[i - 1][j - 1]，
     所以有：$dp[i][j]=\max (dp[i-1][j],dp[i][j-1])$
     综上有：
     $dp[i][j]=\{\begin{array}{ll}0& \text{if }i=0\text{ or }j=0\\ dp[i-1][j-1]+1& \text{if }{S}_1[i-1]=S_2[j-1]\\ \max (dp[i-1][j],dp[i][j-1])& \text{if }{S}_1[i-1]\ne S_2[j-1]\end{array}$

模版

---

int N, M;
int dp[N][M];
 
int lcs(string s1, string s2)
{
	int n = s1.size();
	int m = s2.size();
	
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			if(s1[i - 1] == s2[j - 1])
				dp[i][j] = dp[i - 1][j - 1] + 1;
			else
				dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
	
	return dp[n][m];
}