企业官网建设流程全解析

先明确两个概念：

• 子串：连续的一段字符
• 子序列：不连续、相对顺序不变的字符序列

下面从状态定义、状态转移、初始化、结果取值、DP 表含义、代码逻辑全方位对比。

一、统一前置设定

设：

• 字符串s1长度n，下标1~n（DP 常用从 1 开始，规避越界）
• 字符串s2长度m，下标1~m
• 二维dp[i][j]：s1[1..i]和s2[1..j]对应的 DP 状态

1. 最长公共子串（连续）

1.1 状态定义

dp[i][j]：以 s1 [i]、s2 [j] 为结尾的最长公共连续子串的长度。

关键：必须以当前两个字符结尾，天然约束「连续性」。

1.2 状态转移方程

1. 若s1[i] == s2[j]： \(dp[i][j] = dp[i-1][j-1] + 1\) 解释：当前字符相等，连续子串延长一位，继承左上角状态。

2. 若s1[i] != s2[j]： \(dp[i][j] = 0\) 解释：字符不相等，连续中断，以当前字符结尾的公共子串长度直接置 0。

1.3 初始化

• 第 0 行、第 0 列：dp[0][j] = 0，dp[i][0] = 0空串和任意串无公共子串，长度为 0。

1.4 结果获取

不能直接取dp[n][m]因为dp[n][m]只代表「以两个串最后一位结尾」的公共子串长度，最长子串可能出现在 DP 表任意位置。 需要遍历整个 dp 表，记录全局最大值。

1.5 特点总结

1. 字符不等直接归 0，体现连续性断裂；
2. 状态只依赖左上角dp[i-1][j-1]；
3. 答案是整张 DP 表的最大值；
4. DP 表中非 0 区域是连续斜向增长。

2. 最长公共子序列 LCS（不连续，保顺序）

2.1 状态定义

dp[i][j]：s1[1..i]和s2[1..j]的最长公共子序列长度。

关键：不要求结尾字符匹配，只看两个前缀整体的最优解。

2.2 状态转移方程

1. 若s1[i] == s2[j]： \(dp[i][j] = dp[i-1][j-1] + 1\) 当前字符可纳入子序列，在前缀最优解基础 + 1。

2. 若s1[i] != s2[j]： \(dp[i][j] = \max(dp[i-1][j],\ dp[i][j-1])\) 解释：舍弃s1[i]或者舍弃s2[j]，取两种情况的较大值。

2.3 初始化

和子串一致：dp[0][*] = 0，dp[*][0] = 0，空串 LCS 长度为 0。

2.4 结果获取

直接取dp[n][m]dp[n][m]本身就是两个完整字符串的 LCS 长度，不需要遍历全表。

2.5 特点总结

1. 字符不等时取上方 / 左方最大值，允许跳过字符（对应子序列不连续）；
2. 状态依赖：上、左、左上三个方向；
3. 答案就是 DP 表右下角终点值；
4. DP 值单调非递减，只会变大或不变。

二、核心差异对照表

三、举例直观演示

示例：s1 = "abcde",s2 = "ace"

1. 最长公共子串

公共连续子串：a、c、e，最长长度 = 1 遇到字符不等就置 0，所以没有长连续串。

2. 最长公共子序列

LCS ="ace"，长度 = 3 允许跳过b/d，所以长度更大。

四、极简代码框架（辅助理解差异）

1. 最长公共子串 DP 框架

int n = s1.length(), m = s2.length(); int[][] dp = new int[n+1][m+1]; int maxLen = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (s1.charAt(i-1) == s2.charAt(j-1)) { dp[i][j] = dp[i-1][j-1] + 1; maxLen = Math.max(maxLen, dp[i][j]); } else { dp[i][j] = 0; // 核心区别：不等置0 } } } return maxLen;

2. 最长公共子序列 LCS DP 框架

int n = s1.length(), m = s2.length(); int[][] dp = new int[n+1][m+1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (s1.charAt(i-1) == s2.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[n][m]; // 直接返回右下角

五、一句话总结

1. 子串 DP：盯着「结尾连续」，不相等就清零，答案找全表最大；
2. 子序列 DP：盯着「前缀整体最优」，不相等就选左边 / 上边最优，答案直接用右下角。 这也是两者二维 DP 最本质的分歧。