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

区间动态规划——最长回文子序列长度(C++)

把夜熬成粥,然后喝了它。

——2024年7月1日


书接上回:区间动态规划——最长回文子串(C++)-CSDN博客,大家有想到解决办法吗?

题目描述

        给定一个字符串s(s仅由数字和英文大小写字母组成,长度为1~1000),求s中最长的回文子序列长度。例如,s = “aferegga”,最长的回文子序列为“aerea”,其长度为5。


题解思路

        区间动态规划

下面是个人的思路:

1. 定义dp数组

        定义 dp[i][j]表示 s[i...j] 中最长回文子序列长度。

2. 确定dp限制条件

注:len表示字符串长度

        ①对于任何 len == 1 的字符串,dp[i][j] = 1;

        ②对于任何 len == 2 的字符串,dp[i][j] = dp[i][j-1] + (s[i] == s[j]);

        ③对于任何 len  ≥  3 的字符串,有两种情况:

        如果 s[i] == s[j],那么dp[i][j] = dp[i+1][j-1] + 2

        如果 s[i] != s[j],那么dp[i][j] = max(dp[i+1][j],dp[i][j-1])

解释如下:

        第一种情况,如果字符串长度为1的话,那么它一定是回文子串,长度唯一;

        第二种情况,如果字符串长度为2,那它就有两种可能,要么这两个字符相等,要么不等,不管哪一种情况,这个字符串的回文子序列至少是大于等于1的(第一种情况),如果相等,无非是把这个相等的加上即可。

        第三种情况,字符串长度不小于3时,也有两种可能:
        如果 s[i] == s[j],那么当前最长回文子序列长度就等于上一次的回文子序列长度加上2(两个相同的字符),也可以表示为dp[i][j] = dp[i+1][j-1] + 2*(s[i] == s[j])
        如果 s[i] != s[j],那么当前最长回文子序列长度至少是在 s[i+1....j]和s[i....j-1]中取最大值,即dp[i][j] = max(dp[i+1][j],dp[i][j-1])


推导过程

用矩阵推导如下:

 

代码展示

// 最长回文子序列长度
int getLongestPalind(string s){int size = s.size();vector<vector<int>> dp(size, vector<int> (size, 0));// 定义dp数组// dp[i][j]表示从i到j的最长子回文字符串长度for(int len = 1; len <= size; len++){for(int i = 0; i + len - 1 < size; i++){int j = i + len - 1;if(len == 1){dp[i][j] = 1;}else if(len == 2){dp[i][j] = dp[i][j-1] + (s[i] == s[j]);}else{if(s[i] == s[j]){dp[i][j] = dp[i+1][j-1] + 2 * (s[i] == s[j]);}else{dp[i][j] = max(dp[i+1][j], dp[i][j-1]);}}}}return dp[0][size-1];
}

运行结果

完整代码

// 区间动态规划
#include<iostream>
#include<vector>
#include<string>using namespace std;// 最长回文子序列长度
int getLongestPalind(string s){int size = s.size();vector<vector<int>> dp(size, vector<int> (size, 0));// 定义dp数组// dp[i][j]表示从i到j的最长子回文字符串长度for(int len = 1; len <= size; len++){for(int i = 0; i + len - 1 < size; i++){int j = i + len - 1;if(len == 1){dp[i][j] = 1;}else if(len == 2){dp[i][j] = dp[i][j-1] + (s[i] == s[j]);}else{if(s[i] == s[j]){dp[i][j] = dp[i+1][j-1] + 2 * (s[i] == s[j]);}else{dp[i][j] = max(dp[i+1][j], dp[i][j-1]);}}}}return dp[0][size-1];
}int main(){string s;cout<<"请输入字符串s:";cin>>s;cout<<"最长回文子序列长度为"<<getLongestPalind(s)<<endl;return 0;
}

相关文章:

区间动态规划——最长回文子序列长度(C++)

把夜熬成粥&#xff0c;然后喝了它。 ——2024年7月1日 书接上回&#xff1a;区间动态规划——最长回文子串&#xff08;C&#xff09;-CSDN博客&#xff0c;大家有想到解决办法吗&#xff1f; 题目描述 给定一个字符串s&#xff08;s仅由数字和英文大小写字母组成&#xff0…...

无人机远程控制:北斗短报文技术详解

无人机&#xff08;UAV&#xff09;技术的快速发展和应用&#xff0c;使得远程控制成为了一项关键技术。无人机远程控制涉及无线通信、数据处理等多个方面&#xff0c;其中北斗短报文技术以其独特的优势&#xff0c;在无人机远程控制领域发挥着重要作用。本文将详细解析无人机远…...

240627_关于CNN中图像维度变化问题

240627_关于CNN中图像维度变化问题 在学习一些经典模型时&#xff0c;其中得维度变化关系总搞不太明白&#xff0c;集中学习了以下&#xff0c;在此作以梳理总结&#xff1a; 一般来说涉及到的维度变换都是四个维度&#xff0c;当batch size4&#xff0c;图像尺寸为640*640&a…...

食品行业怎么用JSON群发短信

食品作为日常生活不可缺少的元素&#xff0c;市场需求是很稳定的&#xff0c;但是份额就那么多&#xff0c;商家都要来抢占的话&#xff0c;就需要运营推广各凭本事&#xff0c;市场运营中选择合适的推广方式&#xff0c;可以增加店铺销售额&#xff0c;很多实体店或商城都会建…...

MySQL高级-MVCC-隐藏字段

文章目录 1、介绍2、测试2.1、进入服务器中的 /var/lib/mysql/atguigu/2.2、查看有主键的表 stu2.3、查看没有主键的表 employee2.3.1、创建表 employee2.3.2、查看表结构及其其中的字段信息 1、介绍 ---------------- | id | age | name | ---------------- | 1 | 1 | Js…...

探索PcapPlusPlus开源库:网络数据包处理与性能优化

文章目录 0. 本文概要1. PcapPlusPlus介绍1.1 概述1.2主要特性和功能1.3 PcapPlusPlus 主要模块关系和依赖1.4 网络协议层处理过程 2. 实例2.1 基于 PcapPlusPlus 的应用程序设计和封装流程&#xff1a;2.2 多线程示例代码2.3 代码说明&#xff1a; 3. 程序性能进一步优化3.1 避…...

深入理解SSH:网络安全的守护者

在当今数字化时代&#xff0c;网络安全已成为全球关注的焦点。随着网络攻击手段的不断升级&#xff0c;保护数据传输的安全性变得尤为重要。SSH&#xff08;Secure Shell&#xff09;作为一种安全的网络协议&#xff0c;为远程登录和网络服务提供了强大的安全保障&#xff0c;成…...

DDD学习笔记四

领域模型的构建 基础领域模型的基本组成有名称、属性、关联、职责、事件和异常 发掘领域概念3种策略&#xff1a; 1&#xff09;学习已有系统&#xff0c;重用已有模型 2&#xff09;使用分类标签。分类标签来源于领域&#xff0c;需要我们研究一些资料并做一些提炼。从采用5W…...

Head First设计模式中的典型设计模式解析与案例分析

Head First设计模式中的典型设计模式解析与案例分析 大家好&#xff0c;我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编&#xff0c;也是冬天不穿秋裤&#xff0c;天冷也要风度的程序猿&#xff01; 《Head First设计模式》是一本广受欢迎的书籍&#xff0c…...

iptables 防火墙(一)

iptables 防火墙&#xff08;一&#xff09; 一、Linux 防火墙基础防火墙分类 二、iptables 的表、链结构规则表规则链数据包过滤的匹配流程 三、编写防火墙规则iptables 的安装iptables的基本语法规则的匹配条件通用匹配隐含匹配显式匹配 四、总结 在网络安全的世界里&#xf…...

数据库物理结构设计-定义数据库模式结构(概念模式、用户外模式、内模式)、定义数据库、物理结构设计策略

一、引言 如何基于具体的DBMS产品&#xff0c;为数据库逻辑结构设计的结果&#xff0c;即关系数据库模式&#xff0c;制定适合应用要求的物理结构 1、在设计数据库物理结构前&#xff0c;数据库设计人员首先 要充分了解所用的DBMS产品的功能、性能和特点&#xff0c;包括提供…...

QT加载安装外围依赖库的翻译文件后翻译失败的现象分析:依赖库以饿汉式的形式暴露单例接口导致该现象的产生

1、前提说明 VS2019 QtClassLibaryDll是动态库,QtWidgetsApplication4是应用程序。 首先明确:动态库以饿汉式的形式进行单例接口暴露; 然后,应用程序加载动态库的翻译文件并进行全局安装; // ...QTranslator* trans = new QTranslator();//qDebug() << trans->…...

13_旷视轻量化网络--ShuffleNet V2

回顾一下ShuffleNetV1:08_旷视轻量化网络--ShuffleNet V1-CSDN博客 1.1 简介 ShuffleNet V2是在2018年由旷视科技的研究团队提出的一种深度学习模型&#xff0c;主要用于图像分类和目标检测等计算机视觉任务。它是ShuffleNet V1的后续版本&#xff0c;重点在于提供更高效的模…...

Linux系统编程--进程间通信

目录 1. 介绍 1.1 进程间通信的目的 1.2 进程间通信的分类 2. 管道 2.1 什么是管道 2.2 匿名管道 2.2.1 接口 2.2.2 步骤--以父子进程通信为例 2.2.3 站在文件描述符角度-深度理解 2.2.4 管道代码 2.2.5 读写特征 2.2.6 管道特征 2.3 命名管道 2.3.1 接口 2.3.2…...

docker-本地部署-后端

前置条件 后端文件 这边是一个简单项目的后端文件目录 docker服务 镜像文件打包 #命令行 docker build -t author/chatgpt-ai-app:1.0 -f ./Dockerfile .红框是docker所在文件夹 author&#xff1a;docker用户名chatgpt-ai-app&#xff1a;打包的镜像文件名字:1.0 &#…...

TLS + OpenSSL + Engine + PKCS#11 + softhsm2 安全通信

引擎库路径只有在 /lib 下才能被 "LOAD" 识别到&#xff0c;OpenSSL的ReadMe给的示例在/lib&#xff0c;大概是在构建OpenSSL时默认的configure指定了lib路径 // #define PKCS11_ENGINE_PATH "/usr/lib/x86_64-linux-gnu/engines-1.1/pkcs11.so" #define …...

Unity实现简单的MVC架构

文章目录 前言MVC基本概念示例流程图效果预览后话 前言 在Unity中&#xff0c;MVC&#xff08;Model-View-Controller&#xff09;框架是一种架构模式&#xff0c;用于分离游戏的逻辑、数据和用户界面。MVC模式可以帮助开发者更好地管理代码结构&#xff0c;提高代码的可维护性…...

【简单讲解下OneFlow深度学习框架】

&#x1f3a5;博主&#xff1a;程序员不想YY啊 &#x1f4ab;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f917;点赞&#x1f388;收藏⭐再看&#x1f4ab;养成习惯 ✨希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出…...

FastGPT 调用Qwen 测试Hello world

Ubuntu 安装Qwen/FastGPT_fastgpt message: core.chat.chat api is error or u-CSDN博客 参考上面文档 安装FastGPT后 登录&#xff0c; 点击右上角的 新建 点击 这里&#xff0c;配置AI使用本地 ollama跑的qwen模型 问题&#xff1a;树上有3只鸟&#xff0c;开了一枪&#…...

Golang-GMP

GMP调度 golang-GMP语雀笔记整理 GMP调度设计目的&#xff0c;为何设计GMP?GMP的底层实现几个核心数据结构GMP调度流程 设计目的&#xff0c;为何设计GMP? 无论是多进程、多线程目的都是为了并发提高cpu的利用率&#xff0c;但多进程、多线程都存在局限性。比如多进程通过时…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

Java 二维码

Java 二维码 **技术&#xff1a;**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...

08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险

C#入门系列【类的基本概念】&#xff1a;开启编程世界的奇妙冒险 嘿&#xff0c;各位编程小白探险家&#xff01;欢迎来到 C# 的奇幻大陆&#xff01;今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类&#xff01;别害怕&#xff0c;跟着我&#xff0c;保准让你轻松搞…...