一个串的最长回文子序列的长度

news/2024/7/25 20:46:29/文章来源:https://blog.csdn.net/qinghehe198508/article/details/139075204

题目描述:给定一个字符串str,返回这个字符串的最长回文子序列的长度,比如 str="a12b3c43def2ghi1kpm",最长回文子序列是”1234321" 或者"123c321",返回长度7。

way:转化为求原串和逆序串的最长公共子序列。

way2:f函数,计算str从L到R上的最长回文子序列的长度。要L不要R,要R不要L,要L要R,不要L不要R。终止条件。

//返回str[L...R]的最长回文子序列长度
int f(string s, int L, int R)
{if(L==R) return 1;if(L==R-1){return s[L]==s[R]?2:1;}//要L不要Rint p1=f(s, L, R-1);//要R不要Lint p2=f(s, L+1, R);//不要L不要Rint p3=f(s, L+1, R-1);//要L要Rint p4=f(s, L+1, R-1) +s[L]==s[R]?2:0;return max(p1,max(p2,max(p3,p4)));
}int way(string s)
{int n=s.size();return f(s, 0, n-1);
}

way3:改dp。一定要画图看。

//改dp
int way2(string s)
{int n=s.size();if(n==0) return 0;vector<vector<int>>dp(n, vector<int>(n,0));dp[n-1][n-1]=1;for(int i=0; i<=n-2; i++){dp[i][i]=1;dp[i][i+1]=s[i]==s[i+1]?2:1;}//L从大往小,R从小往大,画图将dp[i][i],dp[i][i+1]填掉也知道L从n-3开始for(int L=n-3; L>=0; L--){for(int R=L+2; R<n; R++){int p1=dp[L][R-1];int p2=dp[L+1][R];int p3=dp[L+1][R-1]+s[L]==s[R]?2:0;dp[L][R]=max(p1,max(p2,p3));}}return dp[0][n-1];
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1052290.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

通过域名接口申请免费的ssl多域名证书

来此加密已顺利接入阿里云的域名接口&#xff0c;用户只需一键调用&#xff0c;便可轻松完成域名验证&#xff0c;从而更高效地申请证书。接下来&#xff0c;让我们详细解读一下整个操作过程。 来此加密官网 免费申请SSL证书 免费SSL多域名证书&#xff0c;泛域名证书。 首先&a…

Jmeter元件及基本作用域

&#x1f680;从今天开始学习性能测试工具——Jmeter&#xff0c;小梦也是先学习了下Jmeter的元件概念以及其基本的作用域&#xff0c;整理了下笔记&#xff0c;希望不管是从事开发领域还是测试领域的朋友们&#xff0c;我们一起学习下Jmeter工具&#xff0c;提升工作中的技能&…

leetcode栈和队列的相关题、有效的括号、用队列实现栈、用栈实现队列、设计循环队列等介绍

文章目录 前言一、有效的括号二、用队列实现栈三、 用栈实现队列四、设计循环队列总结 前言 leetcode栈和队列的相关题、有效的括号、用队列实现栈、用栈实现队列、设计循环队列等介绍 一、有效的括号 leetcode有效的括号 // 动态增长的栈 typedef char STDataType; typedef…

第十七届全国大学生信息安全竞赛创新实践能力赛初赛部分复现

Misc 神秘文件 1.根据提示信息&#xff0c;均需要从ppt中提取信息 2.在ppt的属性中发现一串密文和key&#xff0c;解密之后得到第一部分&#xff0c;根据提示Bifid chipher&#xff0c;为双歧密码解密&#xff0c;使用Bifid Cipher Decode解码 3.在第五张幻灯片&#xff0c;…

微服务实践k8sdapr开发部署调用

前置条件 安装docker与dapr: 手把手教你学Dapr - 3. 使用Dapr运行第一个.Net程序安装k8s dapr 自托管模式运行 新建一个webapi无权限项目 launchSettings.json中applicationUrl端口改成5001,如下: "applicationUrl": "http://localhost:5001" //Wea…

K-means聚类算法详细介绍

目录 &#x1f349;简介 &#x1f348;K-means聚类模型详解 &#x1f348;K-means聚类的基本原理 &#x1f348;K-means聚类的算法步骤 &#x1f348;K-means聚类的优缺点 &#x1f34d;优点 &#x1f34d;缺点 &#x1f348;K-means聚类的应用场景 &#x1f348;K-mea…

mac清理软件推荐免费 mac清理系统数据怎么清理 cleanmymac和腾讯柠檬哪个好

macbook是苹果公司的一款高性能的笔记本电脑&#xff0c;受到了很多用户的喜爱。但是&#xff0c;随着使用时间的增长&#xff0c;macbook的系统也会积累一些垃圾文件&#xff0c;影响其运行速度和空间。那么&#xff0c;macbook系统清理软件推荐有哪些呢&#xff1f;macbook用…

爬虫案例:有道翻译python逆向

pip install pip install requestspip install base64pip install pycrytodome tools 浏览器的开发者工具&#xff0c;重点使用断点&#xff0c;和调用堆栈 工具网站&#xff1a;https://curlconverter.com/ 简便请求发送信息 flow 根据网站信息&#xff0c;preview,respon…

基于 vLLM 搭建 DeepSeek-V2 Chat 服务

直奔主题。 安装vLLM 官方实现的代码还没有 merge 到 vLLM 主分支&#xff0c;所以直接 git clone DeepSeek 的分支。 git clone https://github.com/zwd003/vllm.git cd vllm pip install -e .源码安装大概耗时 10 分钟。 OpenAI 接口规范启动 官方 Github 放的是单条推理…

TS(TypeScript)中Array数组无法调出使用includes方法,显示红色警告

解决方法 打开tsconfig.json文件&#xff0c;添加"lib": ["es7", "dom"]即可。 如下图所示。

php发送短信功能(创蓝短信)

一、以下是创蓝发送短信的功能&#xff0c;可以直接执行&#xff1a; <?php$phone 12312312312;$msg 测试短信功能;echo 发送手机号&#xff1a;.$phone.<br/>;echo 发送内容&#xff1a;.$msg.<br/>;$send sendMessage($phone, $msg);var_dump($send);…

军工单位如何做到安全跨网文件交换与导出的

在现代信息化战争中&#xff0c;军工单位在信息安全方面的需求尤为突出。跨网文件交换与导出作为军工单位日常运营的重要环节&#xff0c;面临着网络带宽限制、数据安全风险、合规性要求和传输稳定性等挑战。下面&#xff0c;我们将从以下几个方面探讨军工单位如何实现安全、高…

2024新数据库入门教程

1.官网下载MySQL 下载Mysql链接: 点击下载mysql 下载完成后解压到某一个文件夹&#xff08;记住这个路径&#xff0c;一会要用到&#xff09; 2.配置初始化文件my.ini 在根目录下创建一个txt文件&#xff0c;名字叫my&#xff0c;文件后缀为ini 以下代码除安装目录和数…

18.分布式监控zabbix-proxy

zabbix proxy 使用场景: 监控远程区域设备监控本地网络不稳定区域当 zabbix 监控上千设备时,使用它来减轻 server 的压力简化分布式监控的维护 环境规划&#xff1a; zabbix-server&#xff1a;外网IP地址192.168.111.66 zabbix-proxy:外网IP地址192.168.111.11 内网IP地址…

【RabbitMQ】使用SpringAMQP的Publish/Subscribe(发布/订阅)

Publish/Subscribe **发布(Publish)、订阅(Subscribe)&#xff1a;**允许将同一个消息发送给多个消费者 **注意&#xff1a;**exchange负责消息路由&#xff0c;而不是存储&#xff0c;路由失败则消息丢失 常见的**X(exchange–交换机)***类型&#xff1a; Fanout 广播Direc…

HNCTF

HNCTF 文章目录 HNCTFBabyPQEZmathez_Classicf(?*?)MatrixRSABabyAESIs this Iso? BabyPQ nc签到题&#xff0c;跟端口连接拿到n和phin n 8336450100232098099043686671148282601664696810002345240872579498695511770993195704402414029892029461830476866385453475141207…

完全背包+背包装满 总结

目录 1.背包恰好装满 &#xff08;1&#xff09;问题是什么 &#xff08;2&#xff09;问题的有效状态和无效状态 &#xff08;3&#xff09;问题的常考形式&#xff0c;以及如何去处理 1.值的大小 2.组合个数 3.排列个数 2.例题 A. Cut Ribbon HDU1114 Piggy-Bank …

冯喜运:5.27黄金短线看震荡,今日黄金原油走势分析

【黄金消息面分析】&#xff1a;黄金作为传统的避险资产&#xff0c;在经济不确定性中扮演着至关重要的角色。近期&#xff0c;国际黄金价格经历了显著的波动。从5月9日的低点2325.19美元/盎司反弹至2340美元/盎司以上&#xff0c;尽管金价曾一度触及2449.89美元/盎司的历史高点…

基于SSM前后端分离版本的论坛系统

目录 前言 一、项目背景 二、相关技术及工具 三、数据库设计 四、软件开发 4.1、搭建环境 4.1.1、创建工程 4.1.2、配置application.yml文件 4.1.3、环境测试 创建测试接口 4.1.4、继续配置 4.2、公共组件 4.2.1、创建工程结构 4.2.2、配置数据源 添加相关依赖 …

如何使用 Re-Ranking 改进大模型 RAG 检索

基于大型语言模型&#xff08;LLMs&#xff09;的聊天机器人可以通过检索增强生成&#xff08;RAG&#xff09;提供外部知识来改进。 这种外部知识可以减少错误答案&#xff08;幻觉&#xff09;&#xff0c;并且使模型能够访问其训练数据中未包含的信息。 通过RAG&#xff0…