最长回文子序列（Longest Palindromic Subsequence, LPS）问题是一个经典的动态规划问题，目标是给定一个字符串，找出其最长的子序列，使得该子序列是回文的（即正读反读相同）

最长回文子序列（Longest Palindromic Subsequence, LPS）问题是一个经典的动态规划问题，目标是给定一个字符串，找出其最长的子序列，使得该子序列是回文的（即正读反读相同）。以下是对该问题的深度剖析，包括问题定义、动态规划解法、代码实现及优化技巧。一、问题定义输入：一个字符串 s（例如 "bbbab"）。输出：s 的最长回文子序列的长度（例如 4，对应子序列 "bbbb"）。特点：子序列可以不连续，但必须保持原字符串的相对顺序。回文要求子序列从左到右和从右到左读相同。二、动态规划解法2.1 思路分析最长回文子序列问题可以通过动态规划解决，因为它具有最优子结构和重叠子问题：最优子结构：一个字符串的最长回文子序列可以通过其子串的最长回文子序列推导。重叠子问题：在递归求解子串的回文子序列时，会重复计算相同的子问题。核心思想是考虑字符串的子串 s[i:j]（从索引 i 到 j），并通过动态规划计算其最长回文子序列的长度。2.2 状态定义定义 dp[i][j] 表示字符串 s[i:j+1]（即子串 s[i:j]，包含 i 和 j）的最长回文子序列的长度。状态的含义：dp[i][j] 是从索引 i 到 j 的子串中最长的回文子序列长度。2.3 状态转移方程对于子串 s[i:j]，根据首尾字符是否相等，分两种情况：如果 s[i] == s[j]：首尾字符可以同时加入回文子序列，长度增加 2。状态转移：dp[i][j] = dp[i+1][j-1] + 2。如果 s[i] != s[j]：