动态规划最长公共子序列

动态规划最长公共子序列问题是计算两个字符串的最长公共子序列的长度，其中子序列是指字符串中按相对顺序但不一定连续出现的字符集合。

动态规划解决最长公共子序列问题的基本思路是，定义一个二维数组dp[i][j]表示字符串A的前i个字符和字符串B的前j个字符的最长公共子序列长度。然后，根据字符串A和B的字符匹配情况分为两种情况：

1. 当A[i] == B[j]时，dp[i][j] = dp[i-1][j-1] + 1，表示当前字符匹配成功，最长公共子序列长度加1。

2. 当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个字符的最长公共子序列长度，取较大值。

最终，dp[m][n]即为字符串A和B的最长公共子序列长度，其中m和n分别为字符串A和B的长度。

相关问题

动态规划 最长公共子序列

最长公共子序列（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)。

动态规划最长公共子序列递归结构

动态规划最长公共子序列的递归结构可以通过以下方式描述：

假设有两个序列a和b，分别有m和n个元素。我们定义一个函数LCS(a, b)来表示序列a和b的最长公共子序列的长度。

当m=0或n=0时，LCS(a, b)的值为0，因为其中一个序列为空，所以它们没有公共子序列。

当a[m-1]等于b[n-1]时，即a的最后一个元素等于b的最后一个元素，那么LCS(a, b)的值可以通过LCS(a[:m-1], b[:n-1])的值加1得到，因为最长公共子序列中包含了这两个相等的元素。

当a[m-1]不等于b[n-1]时，即a的最后一个元素不等于b的最后一个元素，那么LCS(a, b)的值可以通过LCS(a[:m-1], b)和LCS(a, b[:n-1])的值中的较大值得到，因为最长公共子序列要么包含a的最后一个元素，要么包含b的最后一个元素。

综上所述，可以得到递归结构如下：

LCS(a, b) = 0, if m = 0 or n = 0
LCS(a, b) = LCS(a[:m-1], b[:n-1]) + 1, if a[m-1] = b[n-1]
LCS(a, b) = max(LCS(a[:m-1], b), LCS(a, b[:n-1])), if a[m-1] != b[n-1]

这个递归结构可以作为动态规划最长公共子序列问题的基础，通过填充一个二维数组来实现动态规划的解法。每个数组元素dp[i][j]表示序列a[:i]和b[:j]的最长公共子序列的长度。通过填充这个数组，可以得到最终的最长公共子序列的长度。