动态规划是解决最长公共子序列（lcs）最常用且高效的方法，时间复杂度为o(m×n)；状态dpi表示str1前i个字符与str2前j个字符的lcs长度，转移方程分字符相等时dpi=dpi−1+1、不等时dpi=max(dpi−1, dpi)；回溯构造lcs需从dpm逆推，空间可优化为o(min(m,n))但构造序列需完整dp表或路径记录。
动态规划是解决最长公共子序列（LCS）最常用且高效的方法。它不依赖暴力枚举，而是通过复用子问题结果，把时间复杂度从指数级降到 O(m×n)，其中 m、n 分别是两个字符串的长度。
核心状态定义要对齐下标
定义二维数组 dp[i][j] 表示字符串 str1 的前 i 个字符与 str2 的前 j 个字符的 LCS 长度。注意：i 和 j 从 0 开始，但 dp[0][j] 和 dp[i][0] 全为 0（空串与任意串的 LCS 长度为 0），所以实际有效范围是 i ∈ [1, m]，j ∈ [1, n]。
状态转移方程分两种情况
遍历 str1 和 str2 每一对位置（i−1 和 j−1 对应字符）：
- 如果 str1.charAt(i−1) == str2.charAt(j−1)，说明该字符可加入 LCS，dp[i][j] = dp[i−1][j−1] + 1
- 如果不相等，则跳过其中一个字符，取更优解：dp[i][j] = Math.max(dp[i−1][j], dp[i][j−1])
构造具体子序列需回溯
仅求长度只需返回 dp[m][n]；若需还原出实际 LCS 字符串，得从 dp[m][n] 往回走：
- 从 i = m, j = n 开始，逐步比较
- 若 str1[i−1] == str2[j−1]，该字符属于 LCS，加入结果，并同时向左上移动（i--, j--）
- 否则，看 dp[i−1][j] 和 dp[i][j−1] 哪个更大：大者方向即为上一步来源（向上或向左）
- 最后将收集的字符反转，得到正序 LCS
空间可优化但逻辑不变
标准实现用二维数组 O(m×n) 空间；若只需求长度，可用滚动数组压缩为 O(min(m,n)) 空间——只保留两行或一行，每次覆盖更新。但回溯构造字符串时仍需完整 dp 表或额外记录路径（如用 direction 矩阵标记 1/2/3），否则无法还原序列。
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
