当前位置: 首页 > news >正文

最长回文子序列问题

最长回文子序列问题

问题描述:给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。

子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。

注意是子序列而不是子串!
子串是连续的,比如”abda”最长回文子串就是”a”或者”b”…
子序列是不连续的,比如”abda”最长子序列就是”aba”或者”ada”

示例

输入:s = "bbbab"
输出:4
解释:一个可能的最长回文子序列为 "bbbb" 。

子序列问题本身就相对子串、子数组更困难一些,因为前者是不连续的序列,而后两者是连续的,就算穷举你都不一定会,更别说求解相关的算法问题了。

一般来说,这类问题都是让你求一个最长子序列,因为最短子序列就是一个字符。一旦涉及到子序列和最值,考察的是动态规划技巧,时间复杂度一般都是 O(n^2)。

既然要用动态规划,那就要定义 dp 数组,找状态转移关系。

1

int n = array.length;
int[] dp = new int[n];for (int i = 1; i < n; i++) {for (int j = 0; j < i; j++) {dp[i] = 最值(dp[i], dp[j] + ...)}
}

2

int n = arr.length;
int[][] dp = new dp[n][n];for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (arr[i] == arr[j]) dp[i][j] = dp[i][j] + ...elsedp[i][j] = 最值(...)}
}

该文章会更新,欢迎大家批评指正。

推荐一个零声学院免费公开课程,个人觉得老师讲得不错,
分享给大家:[Linux,Nginx,ZeroMQ,MySQL,Redis,
fastdfs,MongoDB,ZK,流媒体,CDN,P2P,K8S,Docker,
TCP/IP,协程,DPDK等技术内容,点击立即学习:
服务器课程:C++服务器

http://www.lryc.cn/news/4555.html

相关文章:

  • 月薪11k!从财务专员到软件测试工程师,成都校区小哥哥用三个月实现转行换岗
  • Android 逆向工具大整理,碉堡了
  • 二维数组的定义
  • SpringMVC--获取请求参数、域对象共享数据
  • 2月13日,30秒知全网,精选7个热点
  • 【C++设计模式】学习笔记(2):模式分类与模版方法 Template Method
  • 【Swift 60秒】92 - Nil coalescing
  • python pip安装的包的路径
  • 个人收藏学习
  • 【C++】类和对象---需掌握的功能
  • 2.12、进程互斥的软件实现方法
  • Java面试题-数据库
  • select 与 where、group by、order by、limit 子句执行优先级比较
  • 【Docker】用开源umami监控你的站点访问量
  • java环境配置
  • Linux系统服务:Apache安装及配置应用
  • 动态规划(Dynamic Programming)——背包问题
  • JVM学习02:内存结构
  • 6年软件测试经验,从我自己的角度理解自动化测试
  • 三种方式查看linux终端terminal是否可以访问外网ping,curl,wget
  • 【Call for papers】SIGCOMM-2023(CCF-A/计算机网络/2023年2月15日截稿)
  • Chapter5:机器人感知
  • [acwing周赛复盘] 第 90 场周赛20230211 补
  • 数组
  • MicroBlaze系列教程(4):AXI_UARTLITE的使用
  • GO 中的 init 函数
  • 使用C#编写k8s CRD Controller
  • Ansible---playbook剧本
  • Delphi 中TImageCollection和TVirtualImageList 控件实现high-DPI
  • Ros中如何给UR5配置自定义工具 | 在Rviz中给UR5机器人装载定义工具 | UR5配置自定义末端执行器