最长公共子序列问题 详细注释

最长公共子序列问题是指给定两个序列，找到它们最长的公共子序列（不要求连续）。例如，对于序列 "ABCDGH" 和 "AEDFHR"，它们的最长公共子序列为 "ADH"。

以下是一个基于动态规划的解法，具体步骤如下：

1. 定义状态：设 $dp[i][j]$ 表示序列 $s1$ 的前 $i$ 个字符和序列 $s2$ 的前 $j$ 个字符的最长公共子序列长度。

2. 初始化：$dp[0][j]=dp[i][0]=0$，表示当其中一个序列为空时，最长公共子序列长度为 0。

3. 状态转移方程：

当 $s1[i-1] = s2[j-1]$，说明两个序列当前字符相同，可以加入最长公共子序列中，因此 $dp[i][j] = dp[i-1][j-1]+1$。

当 $s1[i-1] \ne s2[j-1]$，说明两个序列当前字符不同，最长公共子序列中不包括当前字符，此时有两种选择：

- 在 $s1$ 中去掉当前字符，即 $dp[i][j] = dp[i-1][j]$；
- 在 $s2$ 中去掉当前字符，即 $dp[i][j] = dp[i][j-1]$。

取两种选择中的最大值，即 $dp[i][j] = \max(dp[i-1][j], dp[i][j-1])$。

4. 最终结果：$dp[m][n]$，其中 $m$ 和 $n$ 分别为两个序列的长度。

下面是一个 Python 代码示例：

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

时间复杂度为 $O(mn)$，空间复杂度为 $O(mn)$。