动态规划 最长公共子序列

最长公共子序列（Longest Common Subsequence，LCS）是指给定两个字符串，求它们的最长公共子序列的长度。

动态规划算法可以求解最长公共子序列问题。具体思路如下：

设两个字符串分别为 A 和 B，其长度分别为 m 和 n。

定义一个二维数组 dp，其中 dp[i][j] 表示 A 的前 i 个字符和 B 的前 j 个字符的最长公共子序列的长度。

若 A[i] == B[j]，则 dp[i][j] = dp[i-1][j-1] + 1，即 A 的前 i-1 个字符和 B 的前 j-1 个字符的最长公共子序列的长度加上 A[i] 或 B[j] 就是 A 的前 i 个字符和 B 的前 j 个字符的最长公共子序列的长度。

若 A[i] != B[j]，则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])，即 A 的前 i-1 个字符和 B 的前 j 个字符的最长公共子序列的长度和 A 的前 i 个字符和 B 的前 j-1 个字符的最长公共子序列的长度的最大值就是 A 的前 i 个字符和 B 的前 j 个字符的最长公共子序列的长度。

最终结果为 dp[m][n]，即 A 的前 m 个字符和 B 的前 n 个字符的最长公共子序列的长度。

下面是 Python 代码实现：

def longestCommonSubsequence(text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    dp = [[0] * (n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if text1[i-1] == text2[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)。