当前位置： 首页 > article >正文

代码随想录算法训练营第六十天｜动态规划：647. 回文子串、516.最长回文子序列

article 来源：原创 2023/2/5 15:26:20

【647. 回文子串】

这个题目跟以往不一样的地方在于dp数组及下标的含义和遍历的顺序。

因为题目是求回文子串的个数，那么dp数组的含义是回文子串的个数无法往后推导。需要根据回文这个特性来定义dp数组。

dp[i][j]的含义是区间【i，j】子串是否为回文子串。

递推公式分为两种情况。第一种就是s[i]!=s[j]，那么以【i，j】为区间的子串肯定不是回文。

第二种情况是s[i]==s[j]，那么又可以分为三种情况。

首先是i==j，肯定是回文，因为只有一个字符

其次是i + 1 = j，肯定是回文，因为中间只有一个字符

最后是j - i >1，这样就需要看i+1到j-1这个区间是否为回文，如果是，难么i到j这个区间就是回文，如果不是那么就不是回文。

由此我们可以看到获得dp[i][j]需要从dp[i+1][j-1]得到，所以需要从下往上从左往右遍历，这样才ok。

最后我们来看看最终的代码：

class Solution {
public:int countSubstrings(string s) {vector<vector<bool>>dp(s.size(), vector<bool>(s.size(), false));int res = 0;for(int i = s.size() - 1; i >= 0; i--){for(int j = i; j < s.size(); j++){if(s[i] == s[j]){if(j - i <=1){res++;dp[i][j] = true;}else if(dp[i+1][j-1]){res++;dp[i][j] = true;}}}}return res;}
};

注意：j是从i开始的，因为根据dp数组的定义，j一定比i大。

【516.最长回文子序列】

这个题目最重点的是需要知道递推公式的逻辑。

dp数组的含义是从下标i到下标j最长回文子序列的长度。

我们还是需要去比较s [i]和s[j]是否相等。

如果相等的话，那么dp[i][j] = dp[i+1][j-1] + 2

如果不相等的话，那么就需要比较加入s[i]或者加入s[j]哪一个子串拥有最大的回文序列长度。

dp数组的初始化需要初始化下标i = j的情况，都初始化为1就OK。

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

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章：

代码随想录算法训练营第六十天｜动态规划：647. 回文子串、516.最长回文子序列

【647. 回文子串】这个题目跟以往不一样的地方在于dp数组及下标的含义和遍历的顺序。因为题目是求回文子串的个数&#xff0c;那么dp数组的含义是回文子串的个数无法往后推导。需要根据回文这个特性来定义dp数组。dp[i][j]的含义是区间【i&#xff0c;j】子串是否为回文子串。递…...

编程日记 2023/2/5 15:26:20

C++-继承

文章目录继承切片(赋值兼容规则)继承-作用域隐藏继承-成员函数继承和友元继承和静态成员菱形继承虚继承 virtual public继承-组合要点陈列:继承 继承是使得代码实现最大程度上的复用&#xff0c;是类设计层次的复用 设计一个基础类&#xff0c;将大多数相同属性的放到一个父类…...

编程日记 2023/2/5 15:25:16

Vue：关于插槽的详解

Vue&#xff1a;插槽Slot一、默认插槽1、代码演示2、语法二、具名插槽1、代码演示2、语法3、动态插槽名三、作用域插槽1、渲染作用域2、作用域插槽&#xff08;实战应用&#xff09;&#xff08;1&#xff09;finalList.vue&#xff08;2&#xff09;cardList.vue&#xff08;3…...

编程日记 2023/2/5 15:24:40

【HDFS】从BlockPoolSlice#createRbwFile到BlockReceiver()

BlockPoolSlice#createRbwFile的过程FsDatasetImpl#createRbw的源码详解需要构造BlockReceiver的几种情况讨论从FsDatasetImpl#createRbw，经过FsVolumeImpl#createRbw，最终会调用BlockPoolSlice#createRbwFile的方法。 看下createRbwFile，主要功能就是在rbw目录下根据block…...

编程日记 2023/2/5 15:24:26

Anaconda搭建TensorFlow2.x

本篇文章介绍如何使用Anaconda快速搭建Python环境下的TensorFlow2.x开发框架 Anaconda搭建TensorFlow2.x过程 关于 Anaconda Anaconda就是可以便捷获取包且对包能够进行管理&#xff0c;同时对环境可以统一管理的发行版本。Anaconda包含了conda、Python在内的超过180个科学包…...

编程日记 2023/2/5 15:24:13

Node.js入门：path 模块学习

前言 上文讲解了 Node.js 的 CommonJS 规范&#xff0c;它主要用来解决模块化的问题。从本文开始将会介绍 Node.js 常用的模块&#xff0c;包括内置模块以及好用&#xff0c;好玩的第三方模块。 本篇简单介绍下 path 模块的用法。 path 模块 path 模块提供了用来处理目录和…...

编程日记 2023/2/5 15:24:04

TCP协议的可靠性

TCP作为传输层协议&#xff0c;提供可靠的传输服务。可靠性:保证消息不重复、不丢失、不乱序。如何保证可靠性&#xff1a;TCP协议依据面向连接、流量控制、拥塞控制特性达到可靠的目的。1 三次握手TCP连接建立使用三次握手&#xff0c;三次握手目的是使双方都得到确认&#xf…...

编程日记 2023/2/5 15:23:06

Java项目——文档搜索引擎

文章目录1. 项目概述2. 准备阶段2.1 项目创建2.2 准备静态页面3. 搜索逻辑4. 分词5. 处理 HTML 文件5.1 枚举文件夹中所有文件5.2 预处理文件5.2.1 获取标题5.2.2 获取 URL5.2.3 获取正文6. 索引6.1 正排索引和倒排索引6.2 往正排索引中添加元素6.3 往倒排索引中添加元素6.3.1 …...

编程日记 2023/2/5 15:22:36

yum仓库及NFS共享

目录 yum配置文件及命令 yum配置文件 yum命令详解 本地yum仓库搭建 存储和NFS共享 存储类型 NFS简介 NFS特点 实验 yum配置文件及命令 yum配置文件 主配置文件 /etc/yum.conf #主配置文件 仓库设置文件 /etc/yum.repos.d/*.repo #yum仓库文件位置 日志文件 /v…...

编程日记 2023/2/5 15:21:44

【设计模式之美 设计原则与思想：面向对象】06 | 理论三：面向对象相比面向过程有哪些优势？面向过程真的过时了吗？

在上两节课中&#xff0c;我们讲了面向对象这种现在非常流行的编程范式&#xff0c;或者说编程风格。实际上&#xff0c;除了面向对象之外&#xff0c;被大家熟知的编程范式还有另外两种&#xff0c;面向过程编程和函数式编程。面向过程这种编程范式随着面向对象的出现&#xf…...

编程日记 2023/2/5 15:21:32

Autosar工具汇总

RTE&#xff08;Run Time Environment&#xff09;生成器&#xff1a;用于生成基于AUTOSAR标准的软件体系结构的RTE&#xff0c;包括PDU Router、IPDU、I-Signal等模块&#xff0c;该工具的使用可以极大地简化软件开发的过程。 AUTOSAR架构工具&#xff1a;用于AUTOSAR架构的设…...

编程日记 2023/3/30 12:11:24

如何在DOS上，和ChatGPT聊天？（暴露年龄了吗？

MixGPTMS-DOS是一种早期操作系统&#xff0c;全称为Microsoft Disk Operating System。在上个世纪80年代被广泛使用&#xff0c;成为IBM PC的标准操作系统。作为一个基于命令行的操作系统&#xff0c;用户需要通过键盘输入命令来完成操作。正是因为MS-DOS的成功&#xff0c;为后…...

编程日记 2023/3/30 12:11:15

7天涨粉百万，老九好茶爆火出圈，他做对了什么？

“说卖普洱挣钱&#xff0c;你懂普洱吗&#xff1f;这一片888&#xff0c;光成本都得20”视频中的老九好茶一脸严肃的讲述着行业搞笑段子&#xff0c;该账号将茶行业的内幕&#xff0c;通过“脱口秀”形式呈现出来&#xff0c;获得不少网友的喜欢&#xff0c;近7天涨粉135.43w&…...

编程日记 2023/3/30 12:11:06

【Java】ConcurrentHashMap

ConcurrentHashMap在JDK8中与之前版本实现方式有很大不同。JDK8对ConcurrentHashMap内部的分段锁机制进行了优化和改进，采用了新的数据结构设计，使得其并发性能更加出色。 数据结构 JDK8中的ConcurrentHashMap内部数据结构主要由Node、TreeNode、ForwardingNode、CounterCel…...

编程日记 2023/3/30 12:10:57

Java面试技巧之每天一个Tip——RabbitMQ如何进行消息持久化？

请你说一下RabbitMQ是如何进行消息持久化的&#xff1f; RabbitMQ进行消息持久化包括三个部分&#xff1a; 第一&#xff0c;Exchange&#xff08;交换机&#xff09;持久化&#xff0c;声明时指定Durable&#xff08;英文意思&#xff1a;持久的&#xff09;为True&#xff1…...

编程日记 2023/3/30 12:10:48

介绍几种主流数据迁移工具技术选型，yyds

前言 最近有些小伙伴问我&#xff0c;ETL数据迁移工具该用哪些。 ETL(是Extract-Transform-Load的缩写&#xff0c;即数据抽取、转换、装载的过程)&#xff0c;对于企业应用来说&#xff0c;我们经常会遇到各种数据的处理、转换、迁移的场景。 今天特地给大家汇总了一些目前…...

编程日记 2023/3/30 12:10:28

Flink高手之路3-Flink的入门案例

文章目录Flink高手之路3-Flink的入门案例一、Flink的API二、Flink的编程模型三、Flink的编程步骤四、Flink的入门案例之一&#xff1a;批处理DataSet的处理1.创建一个maven项目2. 改pom文件&#xff0c;引入Flink的依赖3.创建相关的包和类&#xff0c;并测试环境是否搭建成功4.…...

编程日记 2023/3/30 12:10:19

MartriKon OPC Explorer的使用方法

MartriKon OPC Explorer的使用方法 关键词&#xff1a;opc&#xff0c;dcs&#xff0c;foxboro MartriKon OPC Explorer是Foxboro自带的opc测试系统。使用方法简单介绍如下&#xff1a;...

编程日记 2023/3/30 12:10:12

转型成为DevOps

做了8年的运维&#xff0c;接触的技术五花八门&#xff0c;没有自己的核心技能和知识。 从IDC建设到工业互联网项目&#xff0c;作为项目工程师&#xff0c;接触到了所有项目建设类的工作流程。 从硬件运维开始入门&#xff0c;把服务器、网络通讯、电脑终端、视频监控、大屏幕…...

编程日记 2023/3/30 12:10:12

Linux系统监控命令

在学习和使用过程中&#xff0c;汇总整理了一些常用的系统监控命令。 1.top top命令经常用来监控Linux的系统状况&#xff0c;比如cpu、内存的使用&#xff0c;能够实时显示系统中各个进程的资源占用状况&#xff0c;类似于Windows的任务管理器。 第一行&#xff0c;任务队列信…...

编程日记 2023/3/30 12:10:11