LeetCode LCR 095. 最长公共子序列

Categories:

题目描述
思路分析
1. 解法一：动态规划（推荐）
相似题目

题目描述

✅ LCR 095. 最长公共子序列

思路分析

解法一：动态规划（推荐）

核心思路：

经典「双序列 DP」模型。

状态定义：dp[i][j] 表示 text1[0..i-1] 与 text2[0..j-1] 的最长公共子序列（LCS）长度。索引从 1 开始，dp[0][*] = dp[*][0] = 0 作为边界。

状态转移：

若 text1[i-1] == text2[j-1]（当前字符相同），可纳入 LCS： dp[i][j] = dp[i-1][j-1] + 1

否则（字符不同），无法同时使用两个当前字符，丢弃其中一个取最大： dp[i][j] = max(dp[i-1][j], dp[i][j-1])

举例：text1 = "abcde", text2 = "ace"
    ""  a   c   e
""   0   0   0   0
a    0   1   1   1
b    0   1   1   1
c    0   1   2   2
d    0   1   2   2
e    0   1   2   3
dp[5][3] = 3，LCS 为 "ace"。

复杂度分析：

时间复杂度：O(m × n)，其中 m、n 为两字符串长度，需填满二维 dp 表

空间复杂度：O(m × n)，存储 dp 数组；可用滚动数组优化至 O(n)

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 字符相同：当前字符纳入 LCS
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    // 字符不同：丢弃其中一个，取较大值
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
}

func longestCommonSubsequence(text1 string, text2 string) int {
	m, n := len(text1), len(text2)
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			// 字符相同：当前字符纳入 LCS
			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]
}

相似题目

题目	难度	考察点
718. 最长重复子数组	中等	二维DP、最长公共子串
583. 两个字符串的删除操作	中等	二维DP、LCS变种
72. 编辑距离	中等	二维DP、字符串变换
516. 最长回文子序列	中等	二维DP、区间DP
97. 交错字符串	中等	二维DP、字符串匹配
1035. 不相交的线	中等	二维DP、本质是LCS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/75785489