区间动态规划例题：最长回文子序列的长度问题 题目描述 给定一个字符串 s ，找到其中最长的回文子序列的长度，并返回该长度。回文子序列定义为：原字符串中按顺序抽取（不一定连续）的字符组成的序列，且该序列正读反读相同。例如，字符串 "bbbab" 的最长回文子序列是 "bbbb" ，长度为 4； "cbbd" 的最长回文子序列是 "bb" ，长度为 2。 解题思路 问题分析 子序列不要求连续，但必须保持原始顺序。 回文要求序列对称，即首尾字符相同则贡献长度，不同则需舍弃其一。 区间动态规划适合处理此类“子序列在区间内”的问题，通过逐步扩展区间长度来推导最优解。 定义状态 设 dp[i][j] 表示字符串 s 在区间 [i, j] 内的最长回文子序列长度。 目标：求 dp[0][n-1] （ n 为字符串长度）。 状态转移方程 基础情况 ：当区间长度为 1（即 i == j ）时，单个字符本身就是回文， dp[i][j] = 1 。 当 s[i] == s[j] ：首尾字符相同，它们可共同作为回文的一部分，因此 dp[i][j] = dp[i+1][j-1] + 2 。 当 s[i] != s[j] ：首尾字符不同，则最长回文子序列要么在 [i+1, j] 中，要么在 [i, j-1] 中，取最大值： 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] 已计算完毕。 按区间长度 len 从小到大遍历（从 2 到 n ），再遍历起点 i ，通过 j = i + len - 1 确定终点。 逐步计算示例（以 s = "bbbab" 为例） 初始化 ：所有长度为 1 的区间 dp[i][i] = 1 。 长度 len=2 ： [0,1] : s[ 0]='b'=s[ 1] → dp[0][1]=dp[1][0]+2 ，但 i>j 时区间无效，视为 0，故结果为 2。 同理， [1,2] 、 [2,3] 、 [3,4] 首尾相同，均得 2。 长度 len=3 ： [0,2] : s[ 0]='b'=s[ 2]='b' → dp[0][2]=dp[1][1]+2=1+2=3 。 [1,3] : s[ 1]='b'≠s[ 3]='a' → max(dp[2][3]=2, dp[1][2]=2)=2 。 [2,4] : s[ 2]='b'≠s[ 4]='b'？注意 s[ 2]='b', s[ 4]='b'，相同！应为 dp[2][4]=dp[3][3]+2=3 。 长度 len=4 ： [0,3] : s[ 0]='b'≠s[ 3]='a' → max(dp[1][3]=2, dp[0][2]=3)=3 。 [1,4] : s[ 1]='b'=s[ 4]='b' → dp[1][4]=dp[2][3]+2=2+2=4 。 长度 len=5 ： [0,4] : s[ 0]='b'=s[ 4]='b' → dp[0][4]=dp[1][3]+2=2+2=4 。 最终结果： dp[0][4]=4 ，即最长回文子序列长度为 4（如 "bbbb"）。 关键点总结 核心在于首尾字符是否相同的分情况讨论。 遍历顺序需按区间长度由小到大，确保子问题先求解。 时间复杂度 O(n²)，空间复杂度 O(n²)（可优化为 O(n)）。