最长回文子序列 题目描述： 给定一个字符串s，找到其中最长的回文子序列的长度。子序列定义为：不改变剩余字符顺序的情况下，删除某些字符（也可以不删除）形成的新序列。 示例： 输入：s = "bbbab" 输出：4 解释：最长回文子序列是"bbbb" 解题过程： 问题分析 回文子序列与子串不同，不需要连续。我们需要找到字符串中最长的对称序列。 关键观察：一个字符串的最长回文子序列长度取决于： 如果首尾字符相同，它们可以构成回文的一部分 如果首尾字符不同，需要分别考虑去掉首字符或去掉尾字符的情况 定义状态 定义dp[ i][ j ]表示字符串s从索引i到j的子串中最长回文子序列的长度。 状态转移方程 当i = j时：dp[ 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 ]) （首尾不同，选择去掉首或尾的较优解） 遍历顺序 由于dp[ i][ j]依赖于dp[ i+1][ j-1]、dp[ i+1][ j]、dp[ i][ j-1 ]， 我们需要从右下角开始，按对角线方向填充dp表。 具体步骤： 初始化：所有dp[ i][ i ] = 1 按子串长度从2到n遍历： 对于每个起始位置i，结束位置j = i + len - 1 根据状态转移方程计算dp[ i][ j ] 示例演示（s = "bbbab"） 初始状态： dp[ 0][ 0]=1, dp[ 1][ 1]=1, dp[ 2][ 2]=1, dp[ 3][ 3]=1, dp[ 4][ 4 ]=1 长度=2： dp[ 0][ 1]：s[ 0]=b, s[ 1]=b → dp[ 0][ 1] = dp[ 1][ 0 ]+2 = 0+2=2 dp[ 1][ 2]：s[ 1]=b, s[ 2]=b → dp[ 1][ 2] = dp[ 2][ 1 ]+2 = 0+2=2 dp[ 2][ 3]：s[ 2]=b, s[ 3]=a → max(dp[ 3][ 3], dp[ 2][ 2 ]) = max(1,1)=1 dp[ 3][ 4]：s[ 3]=a, s[ 4]=b → max(dp[ 4][ 4], dp[ 3][ 3 ]) = max(1,1)=1 长度=3： dp[ 0][ 2]：s[ 0]=b, s[ 2]=b → dp[ 1][ 1 ]+2 = 1+2=3 dp[ 1][ 3]：s[ 1]=b, s[ 3]=a → max(dp[ 2][ 3], dp[ 1][ 2 ]) = max(1,2)=2 dp[ 2][ 4]：s[ 2]=b, s[ 4]=b → dp[ 3][ 3 ]+2 = 1+2=3 长度=4： dp[ 0][ 3]：s[ 0]=b, s[ 3]=a → max(dp[ 1][ 3], dp[ 0][ 2 ]) = max(2,3)=3 dp[ 1][ 4]：s[ 1]=b, s[ 4]=b → dp[ 2][ 3 ]+2 = 1+2=3 长度=5： dp[ 0][ 4]：s[ 0]=b, s[ 4]=b → dp[ 1][ 3 ]+2 = 2+2=4 最终结果：dp[ 0][ 4 ] = 4 复杂度分析 时间复杂度：O(n²)，需要填充n×(n+1)/2个状态 空间复杂度：O(n²)，使用二维dp数组