区间动态规划例题：最长回文子序列问题 题目描述 给定一个字符串 s ，找出其最长回文子序列的长度。回文子序列是指从原字符串中删除零个或多个字符后，剩余字符按原顺序排列形成的回文串。注意：子序列不要求连续。例如，字符串 "bbbab" 的最长回文子序列是 "bbbb" ，长度为 4； "cbbd" 的最长回文子序列是 "bb" ，长度为 2。 解题思路 定义状态 ：设 dp[i][j] 表示字符串 s 在区间 [i, j] 内的最长回文子序列的长度。 状态转移 ： 若 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 时，单个字符本身就是回文， dp[i][j] = 1 。 当 i > j 时，无效区间， dp[i][j] = 0 。 计算顺序 ：由于依赖 i+1 和 j-1 ，需从区间长度由小到大（即从短子串到长子串）进行递推。 详细步骤 初始化一个二维数组 dp ，大小为 n × n （ n 为字符串长度），所有值初始为 0。 处理长度为 1 的区间：对所有 i ，设置 dp[i][i] = 1 。 枚举区间长度 len 从 2 到 n ： 枚举区间起点 i ，计算终点 j = i + len - 1 （需保证 j < n ）。 若 s[i] == s[j] ： 如果 len == 2 ，直接设置 dp[i][j] = 2 （如 "aa" ）。 否则， 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[0][n-1] 中，表示整个字符串的最长回文子序列长度。 示例分析 以 s = "bbbab" 为例： 初始化后，所有单字符区间值为 1。 长度为 2 的区间： [0,1] : s[0]=='b' 、 s[1]=='b' ，相等， dp[0][1]=2 。 类似处理其他长度为 2 的区间。 长度为 3 的区间： [0,2] : s[0]=='b' 、 s[2]=='b' ，相等， dp[0][2]=dp[1][1]+2=1+2=3 。 最终 dp[0][4] 通过递推得到 4，对应回文子序列 "bbbb" 。 关键点 区间动态规划通过分解子问题避免重复计算。 注意区间长度为 2 时的边界处理，防止 i+1 > j-1 导致越界。 时间复杂度 O(n²)，空间复杂度 O(n²)。