算法 - 最长回文子序列（最长回文数算法）
ztj100 2025-07-15 02:16 15 浏览 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] 二维数组其实就是一个辅助道具，有点像我们在做几何题目中的辅助线。
有了好的 “辅助线”，才能够思路清晰的解题。
相关推荐
- Linux集群自动化监控系统Zabbix集群搭建到实战
-
自动化监控系统...
- systemd是什么如何使用_systemd/system
-
systemd是什么如何使用简介Systemd是一个在现代Linux发行版中广泛使用的系统和服务管理器。它负责启动系统并管理系统中运行的服务和进程。使用管理服务systemd可以用来启动、停止、...
- Linux服务器日常巡检脚本分享_linux服务器监控脚本
-
Linux系统日常巡检脚本，巡检内容包含了，磁盘，...
- 7，MySQL管理员用户管理_mysql 管理员用户
-
一、首次设置密码1.初始化时设置（推荐）mysqld--initialize--user=mysql--datadir=/data/3306/data--basedir=/usr/local...
- Python数据库编程教程:第 1 章 数据库基础与 Python 连接入门
-
1.1数据库的核心概念在开始Python数据库编程之前，我们需要先理解几个核心概念。数据库（Database）是按照数据结构来组织、存储和管理数据的仓库，它就像一个电子化的文件柜，能让我们高效...
- Linux自定义开机自启动服务脚本_linux添加开机自启动脚本
-
设置WGCloud开机自动启动服务init.d目录下新建脚本在/etc/rc.d/init.d新建启动脚本wgcloudstart.sh，内容如下...
- linux系统启动流程和服务管理，带你进去系统的世界
-
Linux启动流程Rhel6启动过程：开机自检bios-->MBR引导-->GRUB菜单-->加载内核-->init进程初始化Rhel7启动过程：开机自检BIOS-->M...
- CentOS7系统如何修改主机名_centos更改主机名称
-
请关注本头条号，每天坚持更新原创干货技术文章。如需学习视频，请在微信搜索公众号“智传网优”直接开始自助视频学习1.前言本文将讲解CentOS7系统如何修改主机名。...
- 前端工程师需要熟悉的Linux服务器(SSH 终端操作)指令
-
在Linux服务器管理中，SSH（SecureShell）是远程操作的核心工具。以下是SSH终端操作的常用命令和技巧，涵盖连接、文件操作、系统管理等场景：一、SSH连接服务器1.基本连接...
- Linux开机自启服务完全指南:3步搞定系统服务管理器配置
-
为什么需要配置开机自启？想象一下：电商服务器重启后，MySQL和Nginx没自动启动，整个网站瘫痪！这就是为什么开机自启是Linux运维的必备技能。自启服务能确保核心程序在系统启动时自动运行，避免人工...
- Kubernetes 高可用(HA)集群部署指南
-
Kubernetes高可用（HA）集群部署指南本指南涵盖从概念理解、架构选择，到kubeadm高可用部署、生产优化、监控备份和运维的全流程，适用于希望搭建稳定、生产级Kubernetes集群...
- Linux项目开发,你必须了解Systemd服务!
-
1.Systemd简介...
- Linux系统systemd服务管理工具使用技巧
-
简介：在Linux系统里，systemd就像是所有进程的“源头”，它可是系统中PID值为1的进程哟。systemd其实是一堆工具的组合，它的作用可不止是启动操作系统这么简单，像后台服务...
- Linux下NetworkManager和network的和平共处
-
简介我们在使用CentoOS系统时偶尔会遇到配置都正确但network启动不了的问题，这问题经常是由NetworkManager引起的，关闭NetworkManage并取消开机启动network就能正...
欢迎 你 发表评论:
- 一周热门
-
-
MySQL中这14个小玩意，让人眼前一亮!
-
旗舰机新标杆 OPPO Find X2系列正式发布 售价5499元起
-
面试官:使用int类型做加减操作，是线程安全吗
-
C++编程知识:ToString()字符串转换你用正确了吗?
-
【Spring Boot】WebSocket 的 6 种集成方式
-
PyTorch 深度学习实战(26):多目标强化学习Multi-Objective RL
-
pytorch中的 scatter_()函数使用和详解
-
与 Java 17 相比，Java 21 究竟有多快?
-
基于TensorRT_LLM的大模型推理加速与OpenAI兼容服务优化
-
这一次，彻底搞懂Java并发包中的Atomic原子类
-
- 最近发表
-
- Linux集群自动化监控系统Zabbix集群搭建到实战
- systemd是什么如何使用_systemd/system
- Linux服务器日常巡检脚本分享_linux服务器监控脚本
- 7，MySQL管理员用户管理_mysql 管理员用户
- Python数据库编程教程:第 1 章 数据库基础与 Python 连接入门
- Linux自定义开机自启动服务脚本_linux添加开机自启动脚本
- linux系统启动流程和服务管理，带你进去系统的世界
- CentOS7系统如何修改主机名_centos更改主机名称
- 前端工程师需要熟悉的Linux服务器(SSH 终端操作)指令
- Linux开机自启服务完全指南:3步搞定系统服务管理器配置
- 标签列表
-
- 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)