区间动态规划例题：最长回文子序列问题（状态转移优化版本） 题目描述 给定一个字符串 s ，找到其中最长的回文子序列的长度。回文子序列定义为原字符串中按顺序（但不一定连续）抽取的字符组成的序列，且该序列正读反读相同。例如，字符串 "bbbab" 的最长回文子序列是 "bbbb" ，长度为 4。 解题过程 本题是区间动态规划的经典问题，但我们可以通过优化状态转移来减少计算量。 定义状态 设 dp[i][j] 表示字符串 s 在区间 [i, j] 内的最长回文子序列的长度。目标是求 dp[0][n-1] （ n 为字符串长度）。 初始化 单个字符一定是回文子序列，长度为 1： dp[i][i] = 1 （对所有 i ）。 若区间长度为 2（即 j = i+1 ），若两字符相同则长度为 2，否则为 1。 状态转移优化 传统区间 DP 会遍历所有区间长度和起点，但我们可以利用回文的对称性优化： 若 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] 时，只需依赖左、下、左下三个方向的值，因此可以按区间长度从小到大计算，避免重复遍历。 计算顺序 按区间长度 len 从 2 到 n 遍历，对每个长度遍历起点 i ，计算终点 j = i + len - 1 。 示例演算 以 s = "bbbab" 为例： 初始化：所有 dp[i][i] = 1 。 长度 2： dp[0][1] = 2 （"bb"）， dp[1][2] = 2 （"bb"）， dp[2][3] = 1 （"ba"）， dp[3][4] = 1 （"ab"）。 长度 3： dp[0][2] = dp[1][1] + 2 = 3 （"bbb"）， dp[1][3] = max(dp[2][3], dp[1][2]) = 2 ， dp[2][4] = max(dp[3][4], dp[2][3]) = 1 。 最终 dp[0][4] = dp[1][3] + 2 = 4 （"bbbb"）。 复杂度分析 时间复杂度 O(n²)，空间复杂度 O(n²)（可优化为 O(n)）。 通过这种优化，我们避免了冗余计算，清晰体现了区间 DP 的递推逻辑。