动态规划详解：LeetCode 1143最长公共子序列算法与Python/C++实现

在算法领域，求解两个序列的公共部分是一个经典问题。本文将深入解析最长公共子序列问题的动态规划解法，并提供清晰的代码实现，帮助你应对面试与刷题挑战。

问题描述

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的子序列是指在原字符串中不改变字符相对顺序的情况下，通过删除某些字符（或不删除）形成的新字符串。例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是。
两个字符串的公共子序列是它们共同拥有的子序列。

示例

输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace"，其长度为 3。

解题思路：动态规划

解决此类字符串匹配与比较问题，动态规划是最高效且清晰的方法之一。核心在于定义状态并找出状态转移方程。

我们定义二维数组 dp[i][j]，表示 text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列长度。

状态转移方程如下：

1. 当 text1[i-1] == text2[j-1] 时，当前字符可以加入公共子序列。
   dp[i][j] = dp[i-1][j-1] + 1
2. 当 text1[i-1] != text2[j-1] 时，当前字符不能同时匹配，则取两个可能方向的最大值。
   dp[i][j] = max(dp[i-1][j], dp[i][j-1])

初始化时，dp[0][j] 和 dp[i][0] 均代表空字符串与另一字符串的匹配，因此值均为0。

下图直观展示了上述状态转移过程：

代码实现

C++ 实现

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int len1 = text1.size();
        int len2 = text2.size();
        // 创建DP表，多出一行一列用于处理边界情况
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));

        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; 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[len1][len2];
    }
};

相关问题：最长公共子串

在面试中（例如阿里曾考察过），常与LCS混淆的是最长公共子串问题。其区别在于子串要求序列必须是连续的。

动态规划解法的核心区别：
当 str1[i-1] != str2[j-1] 时，dp[i][j] 必须置为 0，因为连续性在此中断。

以下Python代码展示了如何求解并返回最长公共子串本身：

class Solution:
    def LCS(self, str1: str, str2: str) -> str:
        m, n = len(str1), len(str2)
        # dp[i][j] 表示以str1[i-1]和str2[j-1]结尾的最长公共子串长度
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        max_length = 0
        end_pos = 0  # 记录最长子串在str1中的结束位置

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if str1[i - 1] == str2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                    if dp[i][j] > max_length:
                        max_length = dp[i][j]
                        end_pos = i - 1  # 转换为0-based索引
                else:
                    dp[i][j] = 0  # 关键区别：不相等时长度归零

        if max_length == 0:
            return ""
        # 根据结束位置和最大长度截取子串
        return str1[end_pos - max_length + 1: end_pos + 1]

总结

最长公共子序列是动态规划的入门经典问题。掌握其状态定义和转移方程，不仅能够解决本题，其思想也广泛应用于文本对比、基因序列对齐等场景。与最长公共子串问题的对比理解，能帮助开发者更深入地把握动态规划中“状态”设计的微妙之处，是准备后端或算法工程师面试的必备知识。