LeetCode -Java 516. 最长回文子序列
发布日期:2021-06-20 05:37:12 浏览次数:11 分类:技术文章

本文共 823 字,大约阅读时间需要 2 分钟。

给定一个字符串s,找到其中最长的回文子序列。可以假设s的最大长度为1000

示例 1:

输入:

"bbbab"

输出:

4

一个可能的最长回文子序列为 "bbbb"。

示例 2:

输入:

"cbbd"

输出:

2

一个可能的最长回文子序列为 "bb"。

分析:

       最小回文子串:子串是连续的。最小回文子序列:可以去掉几个字符。本题类似最小回文子串,采用动态规划,我们假设dp[ i ] [ j ]表示从S字符串中第i到j最长回文子序列的长度。那么状态转换方程为:

dp[i][j] = max{ dp[i+1][j], dp[i][j-1]}  --S[i] !=S[j]      字符不相等,长度为两端最大值

 dp[i][j] = dp[i+1][j-1]+2;    --S[i] ==S[j]      字符相等,长度为内侧子串长度+2

代码:

import java.util.*;/** * @author: Mr.Hu */public class Main{    public static void main(String[] args) {        Scanner sc =new Scanner(System.in);        System.out.println(longestPalindrome(sc.next()));    }    public static int longestPalindrome(String s) {        if (s.length()==0) return 0;        int dp[][]=new int[s.length()][s.length()]; //记录回文子序列长度        for (int i = 0; i < s.length(); i++) { //初始化长度为1和2的dp            dp[i][i]=1;            if (i

 

转载地址:https://blog.csdn.net/h2453532874/article/details/88647669 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:java内存泄漏
下一篇:杭州智慧城市机试题-Java 数组找出无序的个数

发表评论

最新留言

能坚持,总会有不一样的收获!
[***.219.124.196]2024年03月19日 13时32分55秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

华为博士招聘上机考试题目_牛客网-华为-2020届校园招聘上机考试-3 2019-04-21
python中for可以做变量名吗_Python中使用动态变量名的方法 2019-04-21
mysql 日期转换天数_MySQL 日期操作 增减天数、时间转换、时间戳 2019-04-21
java对象去重复_JAVA中List对象去除重复值的方法 2019-04-21
java bss_[转] .bss段和.data段的区别 2019-04-21
java上传图片损坏_大神求助 上传图片后 图片损坏 2019-04-21
java socket唯一标识符_Java Socket编程之常识网络基础知识 2019-04-21
java给xyz大小排序_java递归实现string xyz排序 2019-04-21
arctime必须要java_Arctime使用教程 Arctime常见问题解答 2019-04-21
mysql pxc mysql5.7_mysql之PXC5.7.18集群系列——1. Percona XtraDB Cluster 搭建 2019-04-21
mysql 自适应字段宽度_box-sizing解决自适应布局容器宽度问题 2019-04-21
java 配置文件配置路径_Java读取配置文件路径设置 2019-04-21
vux 选择器_vue中的scoped分析以及在element-UI和vux中的应用 2019-04-21
java cache 有效期_springboot cache 自定义过期时间及自定义缓存key前缀 2019-04-21
java实验一目的_Java实验报告(实验一) 2019-04-21
java+native+字段_+Java中的native关键字浅析(Java+Native+Interface)++ 2019-04-21
php 内存泄露检测工具,php - 诊断内存泄漏 - 允许#bytes的内存大小耗尽 2019-04-21
Java 去除空格获取文件路径 2019-04-21
python 批量修改文件名称去除文件名中空格 2019-04-21
python 将文件名写入 txt文件 2019-04-21