解题思路：动态规划

• 定义状态：

  • 设 $dp[i][j]$ 表示 text1[0:i] 和 text2[0:j] 的 最长公共子序列 的长度。

• 状态转移方程：

  1. 如果 $text1[i-1] == text2[j-1]$，则当前字符匹配：$$dp[i][j] = dp[i-1][j-1] + 1$$
  2. 如果 $text1[i-1] \neq text2[j-1]$，则考虑去掉 text1[i-1] 或 text2[j-1]：$$dp[i][j] = \max(dp[i-1][j], dp[i][j-1])$$

• 初始化：

  • $dp[0][j] = 0$（空字符串与 text2 任何前缀的 LCS 长度为 0）
  • $dp[i][0] = 0$（空字符串与 text1 任何前缀的 LCS 长度为 0）

• 遍历方向：

  • 先遍历 $i$（text1 的前 $i$ 个字符）。
  • 再遍历 $j$（text2 的前 $j$ 个字符）。

• 最终答案：

  • $dp[m][n]$ 即 text1[0:m] 和 text2[0:n] 的最长公共子序列长度。

• 时间复杂度： $O(m \times n)$，其中 $m$ 和 $n$ 分别是 text1 和 text2 的长度。

• 空间复杂度： $O(m \times n)$。

Python 代码

import sys

def longest_common_subsequence(text1, text2):
    """ 使用动态规划计算最长公共子序列长度 """
    m, n = len(text1), len(text2)
    
    # 初始化 DP 数组，dp[i][j] 表示 text1[0:i] 和 text2[0:j] 的最长公共子序列长度
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # 遍历 text1 和 text2
    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:  # 取去掉 text1[i-1] 或 text2[j-1] 的最大值
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    
    return dp[m][n]  # 返回最长公共子序列的长度

def main():
    """ 读取输入并调用求解函数 """
    text1 = sys.stdin.readline().strip()
    text2 = sys.stdin.readline().strip()
    print(longest_common_subsequence(text1, text2))

if __name__ == "__main__":
    main()

Java 代码

import java.util.*;

public class Main {
    public static int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        
        // 初始化 DP 数组，dp[i][j] 表示 text1[0:i] 和 text2[0:j] 的最长公共子序列长度
        int[][] dp = new int[m + 1][n + 1];

        // 遍历 text1 和 text2
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {  // 字符匹配
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {  // 取去掉 text1[i-1] 或 text2[j-1] 的最大值
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];  // 返回最长公共子序列的长度
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String text1 = sc.next();
        String text2 = sc.next();
        System.out.println(longestCommonSubsequence(text1, text2));
        sc.close();
    }
}

C++ 代码

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int longestCommonSubsequence(string text1, string text2) {
    int m = text1.size(), n = text2.size();
    
    // 初始化 DP 数组，dp[i][j] 表示 text1[0:i] 和 text2[0:j] 的最长公共子序列长度
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    // 遍历 text1 和 text2
    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 {  // 取去掉 text1[i-1] 或 text2[j-1] 的最大值
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];  // 返回最长公共子序列的长度
}

int main() {
    string text1, text2;
    cin >> text1 >> text2;  // 读取两个输入字符串
    cout << longestCommonSubsequence(text1, text2) << endl;
    return 0;
}

题目描述

给定两个字符串 text1 和 text2，返回这两个字符串的 最长公共子序列 的长度。如果不存在公共子序列，则返回 0。

定义：

• 子序列：从原字符串中删除 某些字符（可不删除），但不改变剩余字符的 相对顺序，得到的新字符串。
• 公共子序列：两个字符串都包含的 子序列。

输入描述

输入包含两行：

• 第一行是字符串 text1（$1 \leq |text1| \leq 1000$）。
• 第二行是字符串 text2（$1 \leq |text2| \leq 1000$）。

text1 和 text2 仅由小写英文字符组成。

输出描述

输出一行，表示 最长公共子序列 的长度。

样例输入 1

abcde
ace

样例输出 1

3

说明：最长公共子序列是 "ace"，长度为 3。

样例输入 2

abc
abc

样例输出 2

3

说明：最长公共子序列是 "abc"，长度为 3。

样例输入 3

abc
def

样例输出 3

0

说明：两个字符串没有公共子序列，返回 0。