头歌第2关:最长公共子序列

在这一关中，我们将学习如何找到两个字符串的最长公共子序列。

最长公共子序列（LCS）指的是两个字符串中，所有公共的子序列中最长的那个。例如，字符串“ABCD”和“ACDF”中的最长公共子序列为“ACD”。

我们可以使用动态规划来解决这个问题。我们可以创建一个二维数组dp，其中dp[i][j]表示字符串s1的前i个字符和字符串s2的前j个字符的最长公共子序列的长度。

我们可以使用以下递推公式来填充整个数组：

如果s1[i-1] == s2[j-1]，则dp[i][j] = dp[i-1][j-1] + 1，因为当前字符在两个字符串中都出现了，所以我们可以将它添加到最长公共子序列中。

如果s1[i-1] != s2[j-1]，则dp[i][j] = max(dp[i-1][j], dp[i][j-1])，因为当前字符只能添加到s1或s2中的一个子序列中，所以我们需要找到哪个子序列的LCS更长，然后将当前字符添加到该子序列中。

最终，LCS的长度将存储在dp[m][n]中，其中m和n分别是s1和s2的长度。我们可以使用逆推法来找到LCS本身。我们从dp[m][n]开始，如果s1[i-1] == s2[j-1]，则将该字符添加到LCS中，并向左上移动一个位置，否则我们将向左或向上移动一个位置。

下面是一个Python实现的示例代码：

def longest_common_subsequence(s1, s2):
m, n = len(s1), len(s2)
dp = [[0] * (n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
lcs_len = dp[m][n]
lcs = ""
i, j = m, n
while i > 0 and j > 0:
if s1[i-1] == s2[j-1]:
lcs = s1[i-1] + lcs
i -= 1
j -= 1
elif dp[i-1][j] > dp[i][j-1]:
i -= 1
else:
j -= 1
return lcs