动态规划解决最长公共子序列（LCS）问题 问题描述 最长公共子序列（Longest Common Subsequence, LCS）问题是经典的动态规划问题。给定两个字符串（或序列） text1 和 text2 ，返回它们的最长公共子序列的长度。子序列是指从原字符串中删除一些字符（也可以不删除）而不改变剩余字符的相对顺序得到的新字符串。例如， "ace" 是 "abcde" 的子序列，但 "aec" 不是。如果两个字符串没有公共子序列，则返回 0。 解题思路 定义状态 ： 使用二维数组 dp[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符的 LCS 长度。例如， dp[3][2] 表示 text1 的前 3 个字符和 text2 的前 2 个字符的 LCS 长度。 状态转移方程 ： 如果 text1[i-1] == text2[j-1] （当前字符匹配），则 LCS 长度增加 1： dp[i][j] = dp[i-1][j-1] + 1 。 如果字符不匹配，则 LCS 长度继承自之前的最优解： dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 。 初始化边界 ： 当 i=0 或 j=0 时，表示一个字符串为空，此时 LCS 长度为 0： dp[0][j] = 0 , dp[i][0] = 0 。 填表顺序 ： 按行或按列遍历二维数组，确保计算 dp[i][j] 时， dp[i-1][j] 、 dp[i][j-1] 和 dp[i-1][j-1] 已计算完成。 返回结果 ： 最终结果存储在 dp[len(text1)][len(text2)] 中。 逐步示例 以 text1 = "abcde" , text2 = "ace" 为例： 初始化 6×4 的二维数组（长度加 1 用于空字符串情况），第一行和第一列均为 0。 遍历 i=1 到 5（对应 text1 的每个字符）， j=1 到 3（对应 text2 的每个字符）： i=1, j=1 : text1[0]='a' 匹配 text2[0]='a' ， dp[1][1] = dp[0][0] + 1 = 1 。 i=1, j=2 : 'a' 不匹配 'c' ，取 max(dp[0][2]=0, dp[1][1]=1) = 1 。 依此类推，最终 dp[5][3] = 3 （对应 LCS "ace" ）。 优化提示 可压缩状态数组至一维以节省空间（需保留左上角值 prev ）。 若需输出具体 LCS 字符串，需反向追踪 dp 表（通过比较字符和相邻状态）。 通过以上步骤，即可高效求解 LCS 问题。