算法 - 最长回文子序列（最长回文数算法）
ztj100 2025-07-15 02:16 3 浏览 0 评论
~ 题干 ~
首先什么是回文字：
回文字定义：简单解释就是镜像对撑的字符串，例如 “aba”、“abba” 都属于回文字，当然单个字符例如 “a” 也是回文字。
题目：给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
例1：s = "bbbab"，返回4
解释：最长回文子序列为 “bbbb”，长度是4。
例2：s = "cbbd"，返回2
解释：最长回文子序列为 “bb”，长度是2。
限制条件：输入的字符串s只会包含小写英文字母
~ 算法理解 ~
思路：动态规划
通过动态规划的递归式（状态迁移表达式），逐步把问题简单化，直到简单到一眼就可以看出答案（递归边界条件）。
既然是递归的思路，我们应该考虑，如果当前状态已经知道了答案，那再更进一步的条件下能否知道答案。
举例：
如果知道字符串 s1 的最长回文子序列长度为 n1，能否推出 s1 + 某一个字符的最长回文子序列长度？
考虑如下几种情况：
1. 如果 s1 的首尾两个字符是相同的字符：
如上图，很显然，如果首尾两个字符是相同的，那去掉首尾2个字符的最长回文子序列长度为 n1 - 2。
2. 如果 s1 的首尾两个字符是不同的字符：
如上图，如果 s1 首尾两个字符不同，那 s1 的最长回文子序列长度 = max(最长回文子序列m1，最长回文子序列m2)
即：m1 和 m2 哪个大就取哪个。
用一个二维数组dp[i][j]表示从字符串 s 的第 i 位到第 j 位他的最长回文子序列的长度。
可以用如下表表示：（假设字符串 s 长度为10）
如果：i = j，dp[i][j] = 1，因为表示就一个字符，所以最长回文子串长度一定是1
如果：i > j，dp[i][j] = 0, 表示不存在子串，因为第二个下标比第一个下标小
表格变为如下：
如果：i < j，
情况1（i，j位置的2个字符一样）：dp[i][j] = dp[i+1][j-1] + 2
情况2（i，j位置的2个字符不一样）：dp[i][j] = max(dp[i][j-1], dp[i+1][j])
表格如下：
有了状态迁移方程，接下来逐个确定未知方块，根据条件不同，我们可以从 “右上角” 逐步往 “左下角” 推演。
最终最 “左下角” 的位置就是我们要找的答案！
~ 总结 ~
动态规划最关键的是能从题目中抽象出状态转移方程。
例如上题中的 dp[i][j]，整个 dp[i][j] 二维数组其实就是一个辅助道具，有点像我们在做几何题目中的辅助线。
有了好的 “辅助线”，才能够思路清晰的解题。
相关推荐
- Win10预览版10532已知问题汇总（微软win11正式版已知问题一览）
-
IT之家讯微软已向Insider用户推送了Win10预览版10532更新，本次更新对右键菜单、《Windows反馈》应用以及Edge浏览器进行了改进。除此之外还包含一些Bug，汇总如下，有意升级Wi...
- Gabe Aul正测试Win10 Mobile 10532，Insider用户还需等
-
IT之家讯本月中旬微软向Insider用户推送了Win10Mobile预览版10512，该版本修复了一些Bug，增强了系统稳定性，但依然存在一些问题。今天，微软Insider项目负责人GabeAu...
- 微软开始推送Win10预览版10532快速版更新
-
8月28日消息，刚才，微软推送了Win10Build10532快速版，修复了之前的Bug，并带来了三项改进。主要来说，这次的更新改进了右键菜单的UI，使其更具Modern风格（见上图）。此外，更新...
- Win10预览版10532更新内容大全（windows10更新预览版）
-
IT之家讯今天凌晨微软向Insider用户推送了Win10预览版10532快速版更新，本次更新主要带来了三处改进，汇总如下：o改进右键菜单，外观更加Modern。这是基于网友要求界面一致的反馈做出...
- 无法升级Win10预览版10532?也许Hyper-V在搞鬼
-
根据IT之家网友的反映，安装了微软虚拟机Hyper-V的Win10预览版用户无法成功升级Build10532版本，安装过程中会被要求回滚系统。很多朋友在尝试关闭虚拟机之后重启安装程序，结果仍然无法顺...
- Win10预览版10532界面兴起“酷黑”风潮
-
Win10预览版10532的界面改动还是较为明显的，主要体现在右键菜单上面。总体来看，该版本的右键菜单间距更宽，视觉上更大气，操作上更便于触控。具体来说，任务栏右键菜单的变化最为明显。除了增加选项的宽...
- Win10预览版10532上手图集（windows10预览版下载）
-
IT之家讯8月28日，微软今天推送了Win10预览版10532快速版更新，在该版本中，微软主要是加强细节上调整，并且主要是增强Edge浏览器性能等。在Windows10预览版10532中，微软改进了...
- Win10预览版10532上手视频亮点演示
-
IT之家讯8月28日消息，今天凌晨微软向WindowsInsider快速通道用户推送了Win10预览版10532。在Windows10预览版10532中，微软改进了右键菜单，外观更加现代化。另外还...
- 第二篇 前端框架Vue.js（vue前端框架技术）
-
前端三大核心是网页开发的基础，Vue则是基于它们构建的“生产力工具”。通俗理解就是HTML是化妆的工具如眉笔，CSS是化妆品如口红，JavaScript是化妆后的互动，而Vue就是化妆助手。有了化妆工...
- 基于SpringBoot + vue2实现的旅游推荐管理系统
-
项目描述...
- 基于Vue以及iView组件的后端管理UI模板——iview-admin
-
介绍iView-admin是一套后端管理界面模板，基于Vue2.0，iView（现在为ViewUI）组件是一套完整的基于Vue的高质量组件库，虽然Github上有一套非常火的基于ElementUI...
- 别再说你会SPA开发了，这5个核心你真的搞懂了吗?
-
前言此spa非彼spa,不是你所熟知的spa。你所熟知的spa作者肯定是没有你熟悉的。我们这里指的是在前端开发中的一种模型，叫作单页应用程序，顾名思义，就是整个项目只有一个页面，而页面中的内容是动态的...
- React.js Top20面试题（react.js中文官网）
-
概述作为React开发者，对框架的关键概念和原则有扎实的理解是很重要的。考虑到这一点，我整理了一份包含20个重要问题的清单，每个React开发者都应该知道，无论他们是在面试工作还是只是想提高技能。...
- 美媒:特朗普签署行政令后，FBI又发现约2400份、总计超14000页涉肯尼迪遇刺案文件
-
来源：环球时报新媒体1月23日特朗普下令公布肯尼迪遇刺案相关机密文件图源：美媒综合福克斯新闻网和Axios网站10日报道，在总统特朗普签署行政令，要求公布“肯尼迪遇刺案”相关政府机密文件之后，美国...
- 2021 年 Node.js 开发人员学习路线图
-
Node.js自发布以来，已成为业界重要破局者之一。Uber、Medium、PayPal和沃尔玛等大型企业，纷纷将技术栈转向Node.js。Node.js支持开发功能强大的应用，例如实时追踪...
欢迎 你 发表评论:
- 一周热门
- 最近发表
-
- Win10预览版10532已知问题汇总（微软win11正式版已知问题一览）
- Gabe Aul正测试Win10 Mobile 10532，Insider用户还需等
- 微软开始推送Win10预览版10532快速版更新
- Win10预览版10532更新内容大全（windows10更新预览版）
- 无法升级Win10预览版10532?也许Hyper-V在搞鬼
- Win10预览版10532界面兴起“酷黑”风潮
- Win10预览版10532上手图集（windows10预览版下载）
- Win10预览版10532上手视频亮点演示
- 第二篇 前端框架Vue.js（vue前端框架技术）
- 基于SpringBoot + vue2实现的旅游推荐管理系统
- 标签列表
-
- idea eval reset (50)
- vue dispatch (70)
- update canceled (42)
- order by asc (53)
- spring gateway (67)
- 简单代码编程 贪吃蛇 (40)
- transforms.resize (33)
- redisson trylock (35)
- 卸载node (35)
- np.reshape (33)
- torch.arange (34)
- npm 源 (35)
- vue3 deep (35)
- win10 ssh (35)
- vue foreach (34)
- idea设置编码为utf8 (35)
- vue 数组添加元素 (34)
- std find (34)
- tablefield注解用途 (35)
- python str转json (34)
- java websocket客户端 (34)
- tensor.view (34)
- java jackson (34)
- vmware17pro最新密钥 (34)
- mysql单表最大数据量 (35)