最长回文子序列问题
**最长回文子序列问题**
**题目描述**
给定一个字符串 `s`,找出其最长回文子序列的长度。子序列不要求连续,但需保持相对顺序。例如,字符串 `"bbbab"` 的最长回文子序列是 `"bbbb"`,长度为 4。
---
**解题思路**
最长回文子序列问题适合用动态规划解决。核心思路是:**将原问题转化为求原字符串与其反转字符串的最长公共子序列(LCS)**,因为回文正读反读相同。但这里我们直接基于原字符串设计动态规划状态转移。
**步骤分解**
1. **定义状态
2025-11-19 03:32:05
0