区间动态规划例题：最长公共子序列问题 题目描述 给定两个字符串 s1 和 s2 ，长度分别为 m 和 n 。要求找到它们的最长公共子序列（LCS）的长度。子序列是指从原字符串中删除零个或多个字符（不改变剩余字符的相对顺序）得到的新字符串。例如， s1 = "abcde" ， s2 = "ace" 的 LCS 是 "ace" ，长度为 3。 解题过程 1. 定义状态 设 dp[i][j] 表示 s1 的前 i 个字符（即 s1[0:i] ）和 s2 的前 j 个字符（即 s2[0:j] ）的最长公共子序列的长度。 i 的取值范围是 0 到 m （ i=0 表示空字符串）。 j 的取值范围是 0 到 n （ j=0 表示空字符串）。 2. 状态转移方程 基础情况 ： 若 i = 0 或 j = 0 ，即其中一个字符串为空，则 dp[i][j] = 0 （空字符串与任何字符串的 LCS 长度为 0）。 一般情况 （ i > 0 且 j > 0 ）： 若 s1[i-1] == s2[j-1] （当前字符匹配）： dp[i][j] = dp[i-1][j-1] + 1 （匹配的字符贡献一个长度，加上前一部分的 LCS 长度）。 若 s1[i-1] != s2[j-1] （当前字符不匹配）： dp[i][j] = max(dp[i-1][j], dp[i][j-1]) （取跳过 s1 当前字符或跳过 s2 当前字符的较大值）。 3. 初始化 初始化一个大小为 (m+1) x (n+1) 的二维数组 dp ，所有元素初始化为 0。 基础情况已通过初始化覆盖（ i=0 或 j=0 时 dp[i][j]=0 ）。 4. 计算顺序 由于 dp[i][j] 依赖 dp[i-1][j-1] 、 dp[i-1][j] 和 dp[i][j-1] ，需要按行或按列从左到右、从上到下计算。通常使用两层循环： 外层 i 从 1 到 m ，内层 j 从 1 到 n 。 5. 最终结果 结果存储在 dp[m][n] ，即整个字符串 s1 和 s2 的 LCS 长度。 举例说明 以 s1 = "abcde" ， s2 = "ace" 为例： m = 5 ， n = 3 ，初始化 6x4 的 dp 表。 计算过程（只展示部分关键步骤）： i=1, j=1 ： s1[0]='a' ， s2[0]='a' ，匹配， dp[1][1] = dp[0][0] + 1 = 1 。 i=1, j=2 ： s1[0]='a' ， s2[1]='c' ，不匹配， dp[1][2] = max(dp[0][2], dp[1][1]) = max(0,1) = 1 。 i=3, j=2 ： s1[2]='c' ， s2[1]='c' ，匹配， dp[3][2] = dp[2][1] + 1 = 2 （因为 dp[2][1] 对应 "ab" 和 "a" 的 LCS 长度为 1）。 最终 dp[5][3] = 3 ，对应 LCS "ace" 。 复杂度分析 时间复杂度：O(m* n)，需要填充 m*n 个状态。 空间复杂度：O(m* n)，可优化至 O(min(m,n))（仅保留当前行和上一行）。