在 Java 里解决最长公共子序列（LCS）问题时，动态规划是最常用的思路。核心做法是开一个二维数组，用来记录两个字符串前 i 个和前 j 个字符的最长公共子序列长度。这个数组就是动态规划里的“矩阵”，它把每一步的计算结果存起来，避免重复递归。
为什么用数组存储 LCS 矩阵
如果不存中间结果，用纯递归会出现大量重复计算。用数组当备忘录，每个格子只算一次。二维数组 dp[i][j] 的含义是：字符串 A 的前 i 位与字符串 B 的前 j 位的最长公共子序列长度。
状态转移与数组填充
状态转移规则很简单：
- 若 A 的第 i 个字符等于 B 的第 j 个字符，则 dp[i][j] = dp[i-1][j-1] + 1
- 若不相等，则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])
为了处理边界，我们通常把数组开成 (n+1) 行 (m+1) 列，第 0 行和第 0 列初始化为 0。
Java 代码示例
下面是用 Java 数组实现 LCS 矩阵存储与计算的完整例子：
public class LCSArrayDemo {
public static int lcs(String a, String b) {
int n = a.length();
int m = b.length();
// 定义二维数组作为动态规划矩阵，多开一行一列处理空串情况
int[][] dp = new int[n + 1][m + 1];
// 初始化第0行和第0列为0，Java 默认就是0，可省略显式赋值
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a.charAt(i - 1) == b.charAt(j - 1)) {
// 字符相同，左上角加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];
}
public static void main(String[] args) {
String a = "abcde";
String b = "ace";
System.out.println("LCS长度为: " + lcs(a, b));
}
}
数组存储的注意事项
使用数组存矩阵时，要注意字符串下标从 0 开始，而 dp 数组从 1 开始对应字符位置，所以用 charAt(i-1) 取字符。另外如果字符串很长，二维数组会占较多内存，但在一般题目里完全够用。
通过这种方式，你就用最简单的 Java 数组完成了 LCS 动态规划矩阵的存储与计算，后续也可以基于这个矩阵反向追踪出具体的子序列内容。