【LeetCode】动态规划—1143. 最长公共子序列（附完整Python/C++代码）

前言

最长公共子序列问题（LCS, Longest Common Subsequence） 是经典的动态规划问题，要求在两个字符串中找到最长的子序列（不要求子序列连续），使得这个子序列同时出现在两个字符串中。这类问题广泛应用于比较文本相似度、DNA序列分析等领域。我们可以使用动态规划的思想来高效地求解这一问题。

---

题目描述

基本思路

1. 问题定义

给定两个字符串 text1 和 text2，求它们的最长公共子序列的长度。子序列是指从字符串中删除一些或不删除任何字符后得到的序列，但字符的相对顺序不能改变。

举例：

• 输入：text1 = "abcde" 和 text2 = "ace"
• 输出：3，因为最长公共子序列是 "ace"。

2. 理解问题和递推关系

我们可以定义一个二维动态规划数组 dp[i][j]，其中 dp[i][j] 表示 text1 的前 i 个字符与 text2 的前 j 个字符的最长公共子序列长度。

动态规划递推公式：

• 如果 text1[i-1] == text2[j-1]，即当前两个字符相等，则有：
  $$dp[i][j]=dp[i-1][j-1]+1$$
• 如果 text1[i-1] != text2[j-1]，即当前两个字符不相等，则有：
  $$dp[i][j]=\max (dp[i-1][j],dp[i][j-1])$$
  这意味着，我们可以选择：
  • 要么舍弃 text1[i-1]，选择 dp[i-1][j]；
  • 要么舍弃 text2[j-1]，选择 dp[i][j-1]；
  • 我们取这两种情况中的最大值。

边界条件：

• 当 i = 0 或 j = 0 时，即当一个字符串为空时，最长公共子序列长度为 0。因此，dp[0][*] = 0 和 dp[*][0] = 0。

3. 解决方法

动态规划方法

1. 定义 dp[i][j] 表示 text1 的前 i 个字符与 text2 的前 j 个字符的最长公共子序列长度。
2. 通过递推公式进行状态转移。
3. 最终，dp[m][n]（m 和 n 分别是 text1 和 text2 的长度）就是我们需要的结果。

伪代码：

initialize dp array with size (m+1) x (n+1) with 0s
for i from 1 to m:
    for j from 1 to n:
        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]

4. 进一步优化

• 空间优化：由于 dp[i][j] 仅依赖于上一行的状态，因此我们可以用两个一维数组来优化空间复杂度，从 O(m*n) 降低到 O(n)。

5. 小总结

• 递推思路：通过逐步递推，每次比较两个字符是否相等，动态规划解决了这个问题。
• 时间复杂度：该方法的时间复杂度为 O(m*n)，空间复杂度可以通过优化降到 O(n)。

以上就是最长公共子序列问题的基本思路。

---

Python代码

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        
        # 初始化dp数组，大小为(m+1) x (n+1)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        # 填充dp数组
        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]

Python代码解释总结：

1. 初始化：我们创建了一个二维数组 dp，其中 dp[i][j] 表示 text1 的前 i 个字符与 text2 的前 j 个字符的最长公共子序列长度。
2. 动态填充：遍历两个字符串，依照递推关系逐步更新 dp 数组的值。
3. 返回结果：dp[m][n] 即为两个字符串的最长公共子序列的长度。

---

C++代码

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size(), n = text2.size();
        
        // 初始化dp数组，大小为(m+1) x (n+1)
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        
        // 填充dp数组
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                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];
    }
};

C++代码解释总结：

1. 初始化：创建一个二维数组 dp，每个元素初始化为 0。dp[i][j] 用来存储 text1 的前 i 个字符与 text2 的前 j 个字符的最长公共子序列长度。
2. 动态填充：通过遍历两个字符串，使用动态规划的递推公式逐步填充 dp 数组。
3. 返回结果：dp[m][n] 即为两个字符串的最长公共子序列的长度。

---

总结

• 问题核心：最长公共子序列问题要求我们找到两个字符串中最长的公共子序列。通过动态规划可以有效地解决这一问题，时间复杂度为 O(m*n)。
• 优化方向：空间复杂度可以通过使用滚动数组的方式进一步优化到 O(n)。
• 应用场景：最长公共子序列的求解广泛应用于比较文本、DNA序列比对等问题，是一个非常重要的基础算法问题。

原文地址：https://blog.csdn.net/AlbertDS/article/details/142873779

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！