区间动态规划例题：最长回文子序列问题（不同解法版本） 题目描述 给定一个字符串 s ，找到其中最长的回文子序列的长度。回文子序列定义为：从原字符串中删除零个或多个字符后，剩余字符按原顺序排列形成的序列，且该序列正读反读相同。例如，字符串 "bbbab" 的最长回文子序列是 "bbbb" ，长度为 4。 解题思路 本题可通过区间动态规划求解。定义 dp[i][j] 表示字符串 s 在区间 [i, j] 内的最长回文子序列长度。通过比较区间两端字符是否相等，逐步缩小区间范围，最终得到整个字符串的最长回文子序列长度。 步骤详解 状态定义 设 dp[i][j] 表示子串 s[i:j+1] 的最长回文子序列长度（ i 和 j 为闭区间索引）。 初始化 单个字符一定是回文子序列，长度为 1： dp[i][i] = 1 （对所有 i ）。 空区间（ i > j ）视为长度为 0，但本题中不会出现此情况。 状态转移方程 若 s[i] == s[j] ： 两端字符相同，它们可共同构成回文的一部分，因此： dp[i][j] = dp[i+1][j-1] + 2 。 若 s[i] != s[j] ： 两端字符不同，它们不能同时出现在回文子序列中，需分别考虑舍弃左端或右端字符的情况： dp[i][j] = max(dp[i+1][j], dp[i][j-1]) 。 遍历顺序 由于 dp[i][j] 依赖于 dp[i+1][j-1] 、 dp[i+1][j] 和 dp[i][j-1] ，需按区间长度从小到大遍历。 外层循环枚举区间长度 L （从 2 到 n ），内层循环枚举区间起始点 i （ j = i + L - 1 ）。 最终结果 整个字符串的最长回文子序列长度为 dp[0][n-1] 。 示例演示 以 s = "bbbab" 为例（ n = 5 ）： 初始化：所有 dp[i][i] = 1 。 长度 L = 2 ： [0,1] : s[0]=b 、 s[1]=b → dp[0][1] = dp[1][0] + 2 （但 i>j 时视为 0）？实际应直接得 2 。 更正 ：正确计算应为 dp[0][1] = dp[1][0] 无效，直接因两端相等赋值为 2 。 逐步计算后，最终 dp[0][4] = 4 （对应 "bbbb" ）。 复杂度分析 时间复杂度：O(n²)，需填充 n×n 的 DP 表。 空间复杂度：O(n²)，可优化至 O(n)（仅存储当前行和上一行）。