一、回文与子序列：两个概念的“折叠”  

回文的核心是对称：正读与反读相同；子序列的核心是顺序：原串中从左到右挑选字符，不要求相邻。LPS 同时拥抱“对称”与“顺序”，于是天然具备两条性质：  
1. 最优子结构：整个串的最优解可以由更短子串的最优解推出；  
2. 重叠子问题：为了求更长子串，需要反复查询更短子串的结果。  
这两条性质，正是动态规划登场的门票。

二、暴力镜像：最直观的“剪-比对”思路  

最容易想到的算法是：生成所有子序列，逐个检查是否回文，记录最长。  
- 子序列数量：2^n，指数级；  
- 检查回文：O(n)。  
总复杂度 O(n * 2^n)，当 n 超过 20 时，计算时间已突破秒级。暴力法像一面哈哈镜：思路清晰，却扭曲得无法实用。它提醒我们：必须找到“不必生成所有子序列”的捷径。

三、折叠法：从“两端向中心”的第一次降维  

观察回文特征：首尾字符相等时，它们可以同时进入最优解；首尾字符不等时，最优解必然抛弃其中一端，再对剩余串求解。  
于是得到第一条转移思路：  
- 若首尾相等，答案 = 2 + 中间子串的最优解；  
- 若首尾不等，答案 = max(去掉首的子串最优解，去掉尾的子串最优解)。  
这条思路把问题规模从 n 降到 n-1 或 n-2，形成“折叠”效应。它像折纸：每次对折，纸张变短，镜像对称性保持不变。

四、动态规划表：二维矩阵的“镜像坐标系”  

为了存储“中间子串的最优解”，我们定义二维表 dp[i][j]：原串从位置 i 到 j 的最长回文子序列长度。  
- 行号 i 代表“左端点”，列号 j 代表“右端点”；  
- 对角线 i=j 表示单字符，回文长度为 1；  
- 上三角 i>j 无意义，可忽略或置零。  
填表顺序：从“短子串”到“长子串”，即按“子串长度 L”从 2 到 n 逐层计算，确保在计算更长子串时，所依赖的更短子串已就绪。  
这一步像建造一座“镜像坐标系”：每个格子保存一段“折叠后的对称长度”，最终 dp[0][n-1] 就是整张纸对折完毕后的答案。

五、转移方程的“折叠语义”  

填表过程可以口头描述为：  
“先看两端字符是否相等，若相等，就把它们折进去，再去看里面那一层；若不等，就分别尝试去掉左端或右端，选最长的那个。”  
这句口语里藏着转移方程的全部逻辑，也藏着“为什么时间复杂度是 O(n^2)”的直觉：每一对 (i,j) 只计算一次，且常数时间完成判断与取值。  
把“口语”翻译成“心中动画”，你就拥有了“不依赖纸面公式”的永久记忆。

六、边界与初始化：对角线的“镜子起点”  

单字符段 dp[i][i] = 1，这是所有折叠的起始镜面；  
空段 dp[i][i-1] = 0，代表“折叠到尽头”时的基准；  
初始化完成，才能让递推“有底可托”。边界像地基：看不见，却决定整栋楼的平稳。

七、空间优化：从二维到一维的“折叠压缩”  

观察填表顺序：计算 dp[i][j] 时，只依赖“同一行右侧”和“下一行左侧”，即 dp[i+1][j] 与 dp[i][j-1]。  
于是可以把“行”压缩成滚动数组：只用一维表 cur 和 prev，交替更新。  
空间复杂度从 O(n^2) 降到 O(n)，却仍保持 O(n^2) 时间。  
压缩像把折纸拍扁：镜像信息未丢失，只是换了一种“站立方式”。

八、路径还原：让“最长”露出真身

dp[i][j] 只给出长度，要得到具体子序列，需要“路径还原”。  
方法：在填表时同时记录“选择方向”——两端相等则‘折’；不等则记录‘左’或‘右’。  
最后从两端向中心回溯，把选择的字符依次入栈，再翻转输出。  
还原像倒放折纸过程：每一步选择都被记录，最终展开，得到一面完整的镜像。

九、变种与扩展：当“折叠”遇见更多约束

1. 最长回文子串（连续）：用中心扩展或 Manacher，O(n)；
2. 最长回文子序列（删除 k 个）：在 dp 表上加一维“删除预算”；
3. 最长回文子序列（两端插入最少字符）：等价于“n - LPS长度”；
4. 两个字符串的最长公共回文子序列：双 dp 表，O(n^4) 可优化到 O(n^3)；
5. 带权回文：每个字符有权重，dp 转移时累加权重而非计数。  
变种像“折纸艺术”：基础折法不变，却在纸张上加入“剪口”“着色”“多层”，衍生出千姿百态。

十、复杂度与性能：O(n^2) 足够吗？

- 时间：O(n^2) 对于 n=1000 约为 1e6 次运算，现代 CPU 毫秒级完成；
- 空间：O(n) 滚动数组后，1000 长度仅需 8KB，缓存友好；
- 并行：dp[i][*] 行内无依赖，可按行并行，但常数较小，实用价值有限；
- 近似：若 n>5000，可用“采样+贪心”得到近似解，误差 < 5%。  
性能像镜子：够用即可，盲目追求 O(n log n) 反而让代码难读、常数变大。

十一、实际应用：为什么面试爱考 LPS？

- DNA 序列比对：寻找回文重复片段；
- 语音信号处理：寻找对称波形片段；
- 文本编辑器：高亮对称括号、对称单词；
- 验证码生成：生成对称字符串，增加识别难度；
- 数据压缩：回文片段可用“中心+长度”编码，减少存储。  
面试爱考 LPS，是因为它同时考察“动态规划基础”“边界处理”“路径还原”“复杂度分析”四大维度，又能自然延伸到“回文树”“Manacher”“插入最少字符”等进阶话题。

十二、记忆与直觉：把“折叠”刻进肌肉

把 LPS 的解题过程想象成“折纸游戏”：
1. 展开纸张：原串；
2. 对折两端：比较首尾；
3. 留下镜像：相等时折进去；
4. 去掉多余：不等时剪掉短边；
5. 记录折痕：dp 表记录每次选择；
6. 展开成品：路径还原得到回文。  
当你能在脑海里播放这段动画，就不再需要“背诵转移方程”，而是让“折纸直觉”指引你写出代码、画出表格、解释复杂度。

最长回文子序列不是“动态规划”的终点，而是“折叠思维”的起点。它教会我们：把复杂问题拆成“对称子问题”，用“表格记录局部答案”，用“路径还原整体结构”，最终让“镜像”在代码里浮现。下一次，当你面对“需要对称”“需要回文”“需要最优”的任何难题，请想起这篇长文，然后在脑海里展开那张纸，对折、再对折，直到最优解在折痕里清晰可见。