区间动态规划例题：最长回文子序列的长度问题（状态压缩优化版本） 题目描述 给定一个字符串 s ，要求找出其最长回文子序列（Longest Palindromic Subsequence, LPS）的长度。回文子序列不要求连续，但必须保持原字符串中的相对顺序。例如，字符串 "bbbab" 的最长回文子序列是 "bbbb" ，长度为 4。 解题思路 区间动态规划通常定义 dp[i][j] 表示子串 s[i:j+1] 的最长回文子序列长度。通过比较首尾字符是否相等，逐步缩小区间，最终得到整个字符串的解。但基础解法需要 O(n²) 空间，通过状态压缩可优化为 O(n) 空间。 步骤详解 基础状态定义 设 dp[i][j] 表示子串从索引 i 到 j （包含）的最长回文子序列长度。初始时，单个字符的子序列长度为 1（即 dp[i][i] = 1 ）。 状态转移方程 若 s[i] == s[j] ：首尾字符相同，它们一定出现在回文子序列中，因此 dp[i][j] = dp[i+1][j-1] + 2 。 若 s[i] != s[j] ：首尾字符不同，则最长回文子序列要么在 s[i+1:j] 中，要么在 s[i:j-1] 中，取最大值： dp[i][j] = max(dp[i+1][j], dp[i][j-1]) 。 注意：当 j == i+1 且字符相等时，直接赋值为 2（例如 "aa" 的回文子序列长度为 2）。 遍历顺序 由于 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[i][j] 时只需用到下一行（ i+1 ）的数据，因此可用一维数组 dp_prev 存储上一行的结果， dp_curr 存储当前行。 具体实现时，内层循环从右向左更新（避免覆盖未使用的数据），并保留一个变量 pre 记录 dp[i+1][j-1] 的值。 示例演算 （以 s = "bbbab" 为例） 初始化：所有长度为 1 的子序列长度为 1。 长度 2： "bb" →2， "bb" →2， "ba" →1， "ab" →1。 长度 3： "bbb" →首尾相同 "b_b" ，取中间 "b" 的长度 1 + 2 = 3； "bba" →首尾不同，取 max("bb", "ba")=2 。 最终 dp[0][4] 通过递推得到 4（对应子序列 "bbbb" ）。 关键点 状态压缩后空间复杂度降至 O(n)，时间复杂度仍为 O(n²)。 遍历顺序必须保证子区间先于大区间计算。 边界情况（如空串或单字符）需单独处理。 通过以上步骤，即可高效求出任意字符串的最长回文子序列长度。