区间动态规划例题：最长回文子序列问题（状态压缩优化版本） 题目描述 给定一个字符串 s ，找到其中最长的回文子序列的长度，并实现空间复杂度为 O(n) 的解法。回文子序列不要求连续，但必须保持原字符串中的相对顺序。例如，字符串 "bbbab" 的最长回文子序列是 "bbbb"，长度为 4。 解题思路 基础区间DP分析 ： 定义 dp[i][j] 表示子串 s[i:j+1] 的最长回文子序列长度。 当 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]) 。 边界条件：当 i == j 时，单个字符是长度为 1 的回文序列；当 i > j 时，空序列长度为 0。 空间优化策略 ： 基础解法需要 O(n²) 空间。观察状态转移发现， dp[i][j] 仅依赖于下一行（ i+1 ）和当前行左侧（ j-1 ）的值。因此可以压缩为一行，从右向左更新以避免覆盖未使用的状态。 逐步求解 初始化一维数组 ： 创建长度为 n 的数组 dp ，初始时每个元素代表单个字符的回文长度 1（即 dp[i] = 1 ）。 倒序更新 ： 外层循环倒序遍历 i （从末尾到开头），内层循环正序遍历 j （从 i+1 到末尾）。 用变量 pre 记录 dp[i+1][j-1] 的旧值（即上一轮 j-1 对应的 dp[j-1] ）。 若 s[i] == s[j] ，则新值 dp[j] = pre + 2 ；否则 dp[j] = max(dp[j], dp[j-1]) 。 每完成一个 j 的循环后，更新 pre 为当前 dp[j] 的旧值，供下一轮使用。 示例演示（s = "bbbab"） ： 初始： dp = [1,1,1,1,1] 。 i=3 （字符 'a'）： j=4 （'b'）： s[3]!=s[4] ， dp[4]=max(1,1)=1 。 i=2 （字符 'b'）： j=3 ： s[2]!=s[3] ， dp[3]=max(1,1)=1 ； j=4 ： s[2]==s[4] ， pre 记录 j=3 时旧值 1， dp[4]=1+2=3 。 依此类推，最终 dp[4] 即为结果 4。 关键点 内层循环必须从左向右更新，因为 dp[j] 依赖前一个状态 dp[j-1] 。 变量 pre 巧妙保存了斜对角状态，避免二维数组的开销。