<s>Human: 给定两个字符串，编写一个函数来查找它们之间的最长公共子序列。

"ABCDGH", "AEDFHR"
</s><s>Assistant: 这两个字符串之间的最长公共子序列是 "ADH"，它的长度为 3。

思路：

可以使用动态规划来解决这个问题。设字符串1的长度为m，字符串2的长度为n，令dp[i][j]表示字符串1的前i个字符和字符串2的前j个字符之间的最长公共子序列的长度。则有以下状态转移方程：

    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]);

其中，如果字符串1和字符串2在第i个和第j个字符相等，则最长公共子序列的长度应该加上1，并且去掉这个相等的字符后的最长公共子序列的长度应该等于dp[i-1][j-1]。如果不相等，则最长公共子序列长度应该等于分别去掉字符串1第i个字符和字符串2第j个字符后的最长公共子序列长度的最大值，即max(dp[i-1][j], dp[i][j-1])。

最终的答案就是dp[m][n]。

代码实现：


def longestCommonSubsequence(s1: str, s2: str) -> int:
    m = len(s1)
    n = 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])
    return dp[m][n]

s1 = "ABCDGH"
s2 = "AEDFHR"
print(longestCommonSubsequence(s1, s2)) # 输出 3
</s>