最长回文子序列 题目描述： 给定一个字符串 s，找到其中最长的回文子序列的长度。回文子序列定义为：从原字符串中删除零个或多个字符后，剩余字符保持原有顺序并且构成回文。注意，子序列不要求连续。 解题过程： 定义状态 设 dp[ i][ j] 表示字符串 s 在区间 [ i, j] 内的最长回文子序列长度。i 和 j 为字符索引（0 ≤ i ≤ j < n）。 状态转移方程 当 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][ j-1]）、下方（dp[ i+1][ j]）和左下方（dp[ i+1][ j-1 ]）的状态，需从字符串末尾向前遍历 i，从 i+1 向后遍历 j，确保子问题先被计算。 示例推导（s = "bbbab"） 初始化：所有 dp[ i][ i ] = 1。 计算长度为 2 的子串： [ 0,1]：s[ 0]=b, s[ 1]=b → dp[ 0][ 1] = dp[ 1][ 0 ] + 2 = 0+2=2（注意区间无效时取0） [ 1,2]：b≠a → dp[ 1][ 2] = max(dp[ 2][ 2], dp[ 1][ 1 ]) = max(1,1)=1 类似计算完所有长度为 2 的区间。 逐步扩大区间，最终 dp[ 0][ 4 ] = 4（对应回文 "bbbb" 或 "baab"）。 结果 dp[ 0][ n-1 ] 即为整个字符串的最长回文子序列长度。