最长回文子序列问题 题目描述：给定一个字符串s，找到其中最长的回文子序列的长度。子序列定义为不改变剩余字符顺序的情况下删除某些字符（也可以不删除）形成的序列。 解题过程： 问题分析： 回文是正读反读都相同的字符串 子序列不需要连续，但必须保持原始顺序 例如："bbbab"的最长回文子序列是"bbbb"，长度为4 定义状态： 设dp[ i][ j ]表示字符串s从索引i到j（包含两端）的最长回文子序列长度 我们的目标是求dp[ 0][ n-1 ]，其中n是字符串长度 状态转移方程： 情况1：当s[ i] = s[ j ]时 如果i = j，dp[ i][ j ] = 1（单个字符本身就是回文） 如果i + 1 = j，dp[ i][ j ] = 2（两个相同字符） 否则，dp[ i][ j] = dp[ i+1][ j-1 ] + 2（首尾相同，可以同时加入） 情况2：当s[ i] ≠ s[ j ]时 dp[ i][ j] = max(dp[ i+1][ j], dp[ i][ j-1 ])（取去掉首或尾的较大值） 计算顺序： 从短区间到长区间计算 先计算长度为1的区间，然后长度2，3...直到n 保证计算dp[ i][ j]时，dp[ i+1][ j-1]、dp[ i+1][ j]、dp[ i][ j-1 ]都已计算 示例演示（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]=s[ 1]="b" → dp[ 0][ 1 ]=2 dp[ 1][ 2]：s[ 1]≠s[ 2] → max(dp[ 2][ 2], dp[ 1][ 1 ])=1 dp[ 2][ 3]：s[ 2]≠s[ 3 ] → max(1,1)=1 dp[ 3][ 4]：s[ 3]=s[ 4]="b" → dp[ 3][ 4 ]=2 长度3区间： dp[ 0][ 2]：s[ 0]=s[ 2]="b" → dp[ 1][ 1 ]+2=1+2=3 dp[ 1][ 3]：s[ 1]≠s[ 3] → max(dp[ 2][ 3], dp[ 1][ 2 ])=max(1,1)=1 dp[ 2][ 4]：s[ 2]≠s[ 4] → max(dp[ 3][ 4], dp[ 2][ 3 ])=max(2,1)=2 继续计算直到得到dp[ 0][ 4 ]=4 算法实现要点： 时间复杂度O(n²)，空间复杂度O(n²) 注意边界条件：i > j时区间无效，i = j时为基本情况