java中用二维int[][] dp实现lcs动态规划：dpi表示str1前i字符与str2前j字符的lcs长度；初始化(m+1)×(n+1)数组，首行首列为0；按行主序填表，字符相等时dpi=dpi-1+1，否则取上、左最大值；lcs长度为dpm。

在 Java 中用数组实现 LCS 的动态规划矩阵，核心是用二维 int[][] dp 存储子问题解：dp[i][j] 表示 str1 前 i 个字符与 str2 前 j 个字符的最长公共子序列长度。

初始化 dp 数组并处理边界

创建大小为 (m+1) × (n+1) 的数组（m、n 为两字符串长度），首行首列全置 0，对应空字符串与任意前缀的 LCS 长度为 0：

// 示例：str1 = "abc", str2 = "ac"
// dp[0][*] 和 dp[*][0] 全为 0

按行主序填表：状态转移逻辑

从 i=1 到 m、j=1 到 n 遍历：

JavaStoryDevelop

你接手一个需求时，是不是经常这样："改一个小字段 → 结果把不相关的代码也改了"、"需求说得很模糊 → 做着做着发现跑偏了"、"数据库加个字段 → 上线才发现漏了数据兼容"、"做了个新功能 → 一个月后自己都忘了当时怎么设计的"、"写到一半被中断 → 再回来不知道从哪继续"；这个 Skill 就是专门解决这些问题的。 它会自动探测你的项目环境（JDK、Spring Boot、ORM、数据库、前端框架），记在

下载

• 若 str1.charAt(i-1) == str2.charAt(j-1)，则 dp[i][j] = dp[i-1][j-1] + 1
• 否则，dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])

注意下标偏移：字符串索引从 0 开始，而 dp[i][j] 对应前 i、j 个字符，所以比较的是 i-1 和 j-1 处的字符。

获取 LCS 长度与重构子序列（可选）

LCS 长度即 dp[m][n]。如需还原具体子序列，可从 dp[m][n] 反向回溯：

• 若字符相等，将该字符加入结果，并向 dp[i-1][j-1] 移动
• 否则，向 dp[i-1][j] 和 dp[i][j-1] 中较大者移动（相等时任选其一）

回溯路径上收集的字符需反转才是最终 LCS。

空间优化提示（仅长度，不存路径）

若只需长度无需构造序列，可用一维数组滚动更新：
int[] dp = new int[n+1];，遍历时用临时变量保存左上角值，避免覆盖。

Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南