企业官网建设流程全解析

一、完整代码（精简注释）

class Solution { public: int longestCommonSubsequence(string text1, string text2) { int m = text1.length(), n = text2.length(); // dp[i][j] 表示两个字符串前 i、前 j 个字符的最长公共子序列长度 vector<vector<int>> dp(m+1, vector<int>(n+1, 0)); // 遍历两个字符串 for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { // 字符相等，左上角状态加 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]; } };

二、动态规划五步总结

1. 确定 dp 数组及下标含义

vector<vector<int>> dp(m+1, vector<int>(n+1, 0));

dp[i][j] 表示 text1 的前 i 个字符与 text2 的前 j 个字符的最长公共子序列长度。

注意：

• dp 中的 i、j 表示字符数量，不是字符串下标。

• text1 前 i 个字符对应下标 0 到 i-1。

• text2 前 j 个字符对应下标 0 到 j-1。

• 子序列可以不连续，但必须保持原来的相对顺序。

例如：

text1 = "abc" text2 = "ac" dp[2][1]：比较 "ab" 和 "a"，结果为 1 dp[3][2]：比较 "abc" 和 "ac"，结果为 2

2. 确定状态转移方程

分为两种情况。

情况一：当前两个字符相等

if (text1[i-1] == text2[j-1]) { dp[i][j] = dp[i-1][j-1] + 1; }

说明两个字符可以匹配，最长公共子序列长度在左上角状态的基础上加 1。

其中：

• dp[i-1][j-1]：两个字符串都不考虑当前最后一个字符时的最长公共子序列长度。

• +1：将当前匹配成功的字符加入公共子序列。

例如：

text1 = "abc" text2 = "ac" 当前比较 c == c dp[3][2] = dp[2][1] + 1 = 1 + 1 = 2

情况二：当前两个字符不相等

else { dp[i][j] = max(dp[i-1][j], dp[i][j-1]); }

因为两个末尾字符不相等，所以它们不能同时作为公共子序列的最后一个字符。

此时需要考虑两种情况：

• dp[i-1][j]：舍弃 text1 的最后一个字符，保留 text2 的前 j 个字符。

• dp[i][j-1]：舍弃 text2 的最后一个字符，保留 text1 的前 i 个字符。

因为要求最长公共子序列，所以选择两种情况中的最大值。

例如：

text1 = "abc" text2 = "ab" 当前比较 c != b 情况一：舍弃 c "ab" 和 "ab" dp[2][2] = 2 情况二：舍弃 b "abc" 和 "a" dp[3][1] = 1 因此： dp[3][2] = max(2, 1) = 2

核心理解：字符相等就匹配，字符不相等就分别尝试舍弃一个字符，选择更优的结果。

3. 初始化 dp 数组

vector<vector<int>> dp(m+1, vector<int>(n+1, 0));

二维数组大小为 (m+1) × (n+1)，所有元素初始化为 0。

为什么需要加 1？

因为需要额外的一行和一列表示空字符串。

dp[0][j] = 0：text1 为空字符串 dp[i][0] = 0：text2 为空字符串

只要其中一个字符串为空，最长公共子序列长度就为 0。

这样可以直接从 dp[1][1] 开始计算，不需要单独处理边界。

特别注意：

dp[i][j] // 前 i 个字符和前 j 个字符 text1[i-1] // text1 前 i 个字符中的最后一个 text2[j-1] // text2 前 j 个字符中的最后一个

4. 确定遍历顺序

for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { // 状态转移 } }

遍历顺序：从上到下、从左到右。

因为计算 dp[i][j] 时，依赖三个位置：

dp[i-1][j-1]：左上方 dp[i-1][j]：上方 dp[i][j-1]：左方

所以必须保证这三个位置已经计算完成，才能计算当前位置。

外层循环负责遍历 text1，内层循环负责遍历 text2，不断更新二维 dp 数组。

5. 举例推导 dp 数组

假设：

text1 = "abc"; text2 = "ab";

最终 dp 数组为：

空 a b 空 0 0 0 a 0 1 1 b 0 1 2 c 0 1 2

计算过程：

dp[1][1]： a == a dp[1][1] = dp[0][0] + 1 = 1 dp[1][2]： a != b dp[1][2] = max(dp[0][2], dp[1][1]) = 1 dp[2][1]： b != a dp[2][1] = max(dp[1][1], dp[2][0]) = 1 dp[2][2]： b == b dp[2][2] = dp[1][1] + 1 = 2 dp[3][1]： c != a dp[3][1] = max(dp[2][1], dp[3][0]) = 1 dp[3][2]： c != b dp[3][2] = max(dp[2][2], dp[3][1]) = 2

最终：

return dp[m][n]; // 返回 dp[3][2] = 2

最长公共子序列为 "ab"，长度为 2。

三、复杂度分析

时间复杂度：O(m * n)

使用两层循环遍历两个字符串，每个 dp 状态只计算一次。

空间复杂度：O(m * n)

创建了一个 (m+1) × (n+1) 的二维 dp 数组，用于保存所有子问题的结果。

四、核心总结

1. 本题使用二维动态规划，求两个字符串的最长公共子序列长度。子序列不要求连续，但是必须保持字符的相对顺序。

2. dp[i][j] 表示 text1 前 i 个字符和 text2 前 j 个字符的最长公共子序列长度。

3. dp 数组大小为 (m+1) × (n+1)，多出来的第一行和第一列表示空字符串，全部初始化为 0。

4. dp 中的 i、j 表示字符数量，而字符串下标从 0 开始，因此比较字符时使用 text1[i-1] 和 text2[j-1]。

5. 当两个字符相等时，说明当前字符可以匹配，状态转移为 dp[i][j] = dp[i-1][j-1] + 1。

6. 当两个字符不相等时，分别考虑舍弃 text1 的最后一个字符和舍弃 text2 的最后一个字符，选择公共子序列长度较大的结果，即 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

7. 遍历顺序为从上到下、从左到右，因为当前状态依赖左上方、上方和左方已经计算完成的状态。

8. 整个 dp 是一个二维数组，每个位置保存对应两个字符串前缀的最长公共子序列长度，最终返回右下角的 dp[m][n]。

9. 时间复杂度为 O(mn)，空间复杂度为 O(mn)。

最重要的代码模板

// 当前字符相等 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]); }

一句话记忆：字符相等，左上角加 1；字符不相等，上方和左方取最大值。

这道题最重要的就是理解dp[i][j]的含义，以及为什么字符不相等时需要分别舍弃一个字符。