代码随想录 NO52 | 动态规划_leetcode 647. 回文子串 516.最长回文子序列
动态规划_leetcode 647. 回文子串 516.最长回文子序列
今天是动态规划最后一天的题了,整个过程已经接近尾声了!
647. 回文子串

-
确定dp数组(dp table)以及下标的含义
本题如果我们定义,dp[i] 为 下标i结尾的字符串有 dp[i]个回文串的话,我们会发现很难找到递归关系。
dp[i] 和 dp[i-1] ,dp[i + 1] 看上去都没啥关系。
在判断字符串S是否是回文,那么如果知道 s[1],s[2],s[3] 这个子串是回文的,那么只需要比较 s[0]和s[4]这两个元素是否相同,如果相同的话,这个字符串s 就是回文串。
那么此时是不是能找到一种递归关系,也就是判断一个子字符串(字符串的下表范围[i,j])是否回文,依赖于,子字符串(下表范围[i + 1, j - 1])) 是否是回文。
所以为了明确这种递归关系,dp数组是要定义成一位二维dp数组。
布尔类型的dp[i][j]:表示区间范围[i,j] (注意是左闭右闭)的子串是否是回文子串,如果是dp[i][j]为true,否则为false。 -
确定递推公式
整体上是两种,就是s[i]与s[j]相等,s[i]与s[j]不相等这两种。- 当s[i]与s[j]不相等,那没啥好说的了,dp[i][j]一定是false。
- 当s[i]与s[j]相等时,这就复杂一些了,有如下三种情况
- 情况一:下标i 与 j相同,同一个字符例如a,当然是回文子串
- 情况二:下标i 与 j相差为1,例如aa,也是回文子串
- 情况三:下标:i 与 j相差大于1的时候,例如cabac,此时s[i]与s[j]已经相同了,我们看i到j区间是不是回文子串就看aba是不是回文就可以了,那么aba的区间就是 i+1 与 j-1区间,这个区间是不是回文就看dp[i + 1][j - 1]是否为true。
if s[i] == s[j]:if j - i <= 1:result += 1dp[i][j] = Trueelif dp[i + 1][j - 1]:result += 1dp[i][j] = True
-
dp数组如何初始化
dp[i][j]可以初始化为true么? 当然不行,怎能刚开始就全都匹配上了。
所以dp[i][j]初始化为false。 -
确定遍历顺序
首先从递推公式中可以看出,情况三是根据dp[i + 1][j - 1]是否为true,在对dp[i][j]进行赋值true的。
dp[i + 1][j - 1] 在 dp[i][j]的左下角,如图:

所以一定要从下到上,从左到右遍历,这样保证dp[i + 1][j - 1]都是经过计算的。 -
举例推导dp数组

class Solution:def countSubstrings(self, s: str) -> int:dp = [[False] * len(s) for _ in range(len(s))]result = 0for i in range(len(s)-1, -1, -1): #注意遍历顺序for j in range(i, len(s)):if s[i] == s[j]:if j - i <= 1: #情况一 和 情况二result += 1dp[i][j] = Trueelif dp[i+1][j-1]: #情况三result += 1dp[i][j] = Truereturn result
516.最长回文子序列

- 确定dp数组(dp table)以及下标的含义
dp[i][j]:字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。 - 确定递推公式
- 在判断回文子串的题目中,关键逻辑就是看s[i]与s[j]是否相同。
如果s[i]与s[j]相同,那么dp[i][j] = dp[i + 1][j - 1] + 2; - 如果s[i]与s[j]不相同,说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子序列的长度,那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。
加入s[j]的回文子序列长度为dp[i + 1][j]。
加入s[i]的回文子序列长度为dp[i][j - 1]。
那么dp[i][j]一定是取最大的,即:dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
- 在判断回文子串的题目中,关键逻辑就是看s[i]与s[j]是否相同。
- dp数组如何初始化
首先要考虑当i 和j 相同的情况,从递推公式:dp[i][j] = dp[i + 1][j - 1] + 2; 可以看出 递推公式是计算不到 i 和j相同时候的情况。
所以需要手动初始化一下,当i与j相同,那么dp[i][j]一定是等于1的,即:一个字符的回文子序列长度就是1。
其他情况dp[i][j]初始为0就行,这样递推公式:dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); 中dp[i][j]才不会被初始值覆盖。 - 确定遍历顺序
从递归公式中,可以看出,dp[i][j] 依赖于 dp[i + 1][j - 1] ,dp[i + 1][j] 和 dp[i][j - 1],如图:

所以遍历i的时候一定要从下到上遍历,这样才能保证下一行的数据是经过计算的。
j的话,可以正常从左向右遍历。 - 举例推导dp数组

class Solution:def longestPalindromeSubseq(self, s: str) -> int:dp = [[0 for _ in range(len(s))] for _ in range(len(s))]for i in range(len(s)):dp[i][i] = 1for i in range(len(s)-1,-1,-1):for j in range(i+1,len(s)):if s[i] == s[j]:dp[i][j] = dp[i+1][j-1] +2else:dp[i][j] = max(dp[i][j-1], dp[i+1][j])return dp[0][-1]
今天这两道题还挺绕的,第一题数组定义不能再根据以往经验来以最后一个字符为限,另外遍历顺序也有所不同!
相关文章:
代码随想录 NO52 | 动态规划_leetcode 647. 回文子串 516.最长回文子序列
动态规划_leetcode 647. 回文子串 516.最长回文子序列今天是动态规划最后一天的题了,整个过程已经接近尾声了! 647. 回文子串 确定dp数组(dp table)以及下标的含义 本题如果我们定义,dp[i] 为 下标i结尾的字符串有 dp…...
【数据挖掘】1、综述:背景、数据的特征、数据挖掘的六大应用方向、有趣的案例
目录一、背景1.1 学习资料1.2 数据的特征1.3 数据挖掘的应用案例1.4 获取数据集1.5 数据挖掘的定义二、分类三、聚类四、关联分析五、回归六、可视化七、数据预处理八、有趣的案例8.1 隐私保护8.2 云计算的弹性资源8.3 并行计算九、总结一、背景 1.1 学习资料 推荐书籍如下&a…...
【架构师】零基础到精通——康威定律
博客昵称:架构师Cool 最喜欢的座右铭:一以贯之的努力,不得懈怠的人生。 作者简介:一名Coder,软件设计师/鸿蒙高级工程师认证,在备战高级架构师/系统分析师,欢迎关注小弟! 博主小留言…...
Could not extract response: no suitable HttpMessageConverter
版本:spring-cloud-openfeign-core-2.1.1.RELEASE.jar,spring-webmvc-5.1.14.RELEASE.jar,jetty-server-9.4.41.v20210516.jar,tomcat-embed-core-9.0.48.jar 问题背景 生产服务请求下游服务时偶发抛出下面的异常,下…...
文献计量三大定律之一---洛特卡定律及普赖斯定律
科学生产率是洛特卡定律的基础,科学生产率”(Scientific Productivity))是指科学家(科研人员)在科学上所表现出的能力和工作效率,通常用其生产的科学文献的数量来衡量。 1926年,洛特卡在一篇论文中提出了科…...
2023年软考高级网络规划设计师
网络规划设计师是软考高级考试科目之一,也是比较难的科目,据官方数据统计网规每年的通过率很低,而且每年只有下半年11月份考一次,如果是直接裸考,估计很悬哦~ 但是你参加考试获得证书的过程就是一个学习网络规划系统知…...
数据治理驱动因素 -报考题
数据治理并不是到此为止,而是需要直接与企业战略保持一致。数据治理越显著地帮助解决组织问题,人们越有可能改变行为、接受数据治理实践。数据治理的驱动因素大多聚焦于减少风险或者改进流程。(1)减少风险1)一般性风险…...
2023淘宝天猫38节红包满减优惠活动时间是从几月几号什么时候开始?
2023年淘宝天猫38节活动将于2023年3月2日中午12点正式开始,活动将持续至2023年3月8日晚上23点59分。届时,淘宝天猫将推出一系列的优惠活动和红包福利,为广大女性用户送上节日的祝福和福利。在这个特别的节日里,淘宝天猫为女性用户…...
Hive表优化、表设计优化、Hive表数据优化(ORC)、数据压缩、存储优化
文章目录Hive表优化Hive表设计优化分区表结构 - 分区设计思想分桶表结构 - Join问题Hive中的索引Hive表数据优化常见文件格式TextFileSequenceFileParquetORC数据压缩存储优化 - 避免小文件生成存储优化 - 合并输入的小文件存储优化 - ORC文件索引Row Group IndexBloom Filter …...
LearnOpenGL-入门-着色器
本人刚学OpenGL不久且自学,文中定有代码、术语等错误,欢迎指正 我写的项目地址:https://github.com/liujianjie/LearnOpenGLProject LearnOpenGL中文官网:https://learnopengl-cn.github.io/ 文章目录着色器GLSL数据类型输入与输…...
【谷粒学院】vue、axios、element-ui、node.js(44~58)
44.前端技术-vue入门 🧨Vue.js 是什么 Vue (读音 /vjuː/,类似于 view) 是一套用于构建用户界面的渐进式框架。 Vue 的核心库只关注视图层,不仅易于上手,还便于与第三方库或既有项目整合。另一方面,当与现代化的工具…...
【一些回忆】2022.02.26-2023.02.26 一个普通男孩的365天
💃🏼 本人简介:男 👶🏼 年龄:18 🤞 作者:那就叫我亮亮叭 📕 专栏:一些回忆 为什么选择在这个时间节点回忆一下呢? 一是因为今天距离2023高考仅剩1…...
OSPF的多区域特性 (电子科技大学TCP/IP实验三)
一.实验目的 1、掌握OSPF 协议中区域的类型、特征和作用 2、掌握OSPF 路由器的类型、特征和作用 3、掌握OSPF LSA 分组的类型、特征和作用 4、理解OSPF 区域类型、路由器类型和OSPF LSA 分组类型间的相互关系 二.预备知识 1、静态路由选择和动态路…...
(四十四)多个事务更新同一行数据时,是如何加锁避免脏写的?
之前我们已经用很多篇幅给大家讲解了多个事务并发运行的时候,如果同时要读写一批数据,此时读和写时间的关系是如何协调的,毕竟要是你不协调好的话,可能就会有脏读、不可重复读、幻读等一系列的问题。 简单来说,脏读、…...
【数据库】第十二章 数据库管理
第12章 数据库管理 数据库的物理存储 关于内存、外存、磁盘、硬盘、软盘、光盘的区别_Allenzyg的博客-CSDN博客_磁盘和硬盘的区别 数据库记录在磁盘上的存储 定长,变长跨块,非跨快 文件的组织方方法: 无序记录文件(堆文件heap或pile file…...
Redis源码---整体架构
目录 前言 Redis目录结构 前言 deps目录 src 目录 tests 目录 utils 目录 重要的配置文件 Redis 功能模块与源码对应 前言 服务器实例 数据库数据类型与操作 高可靠性和高可扩展性 辅助功能 前言 以先面后点的方法推进无特殊说明,都是基于 Redis 5.0.…...
基于springboot+vue的校园招聘系统
博主主页:猫头鹰源码 博主简介:Java领域优质创作者、CSDN博客专家、公司架构师、全网粉丝5万、专注Java技术领域和毕业设计项目实战 主要内容:毕业设计(Javaweb项目|小程序等)、简历模板、学习资料、面试题库、技术咨询 文末联系获取 项目介绍…...
SAP MM学习笔记1-SAP中扩张的概念,如何将一个物料从工厂A扩张到工厂B
MM中在创建物料的时候,最低也得创建如下5个view。 基本数据1 基本数据2 购买管理 会计1 会计2 1,扩张是什么 有时候,你想增加其他的View,比如保管场所 等,你不能用MM02来做编辑,要用MM01来做扩张。这就是扩…...
【Python】Numpy数组的切片、索引详解:取数组的特定行列
【Python】Numpy数组的切片、索引详解:取数组的特定行列 文章目录【Python】Numpy数组的切片、索引详解:取数组的特定行列1. 介绍2. 切片索引2.1 切片索引先验知识2.1 一维数组的切片索引2.3 多维数组的切片索引3. 数组索引(副本)…...
2023年全国最新交安安全员精选真题及答案6
百分百题库提供交安安全员考试试题、交安安全员考试预测题、交安安全员考试真题、交安安全员证考试题库等,提供在线做题刷题,在线模拟考试,助你考试轻松过关。 51.安全生产资金保障制度建立后关键在于落实,各施工企业在落实安全生…...
Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误
HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误,它们的含义、原因和解决方法都有显著区别。以下是详细对比: 1. HTTP 406 (Not Acceptable) 含义: 客户端请求的内容类型与服务器支持的内容类型不匹…...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...
基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...
springboot 日志类切面,接口成功记录日志,失败不记录
springboot 日志类切面,接口成功记录日志,失败不记录 自定义一个注解方法 import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java.lang.annotation.RetentionPolicy; import java.lang.annotation.Target;/***…...
《Docker》架构
文章目录 架构模式单机架构应用数据分离架构应用服务器集群架构读写分离/主从分离架构冷热分离架构垂直分库架构微服务架构容器编排架构什么是容器,docker,镜像,k8s 架构模式 单机架构 单机架构其实就是应用服务器和单机服务器都部署在同一…...
从物理机到云原生:全面解析计算虚拟化技术的演进与应用
前言:我的虚拟化技术探索之旅 我最早接触"虚拟机"的概念是从Java开始的——JVM(Java Virtual Machine)让"一次编写,到处运行"成为可能。这个软件层面的虚拟化让我着迷,但直到后来接触VMware和Doc…...
Java数组Arrays操作全攻略
Arrays类的概述 Java中的Arrays类位于java.util包中,提供了一系列静态方法用于操作数组(如排序、搜索、填充、比较等)。这些方法适用于基本类型数组和对象数组。 常用成员方法及代码示例 排序(sort) 对数组进行升序…...
goreplay
1.github地址 https://github.com/buger/goreplay 2.简单介绍 GoReplay 是一个开源的网络监控工具,可以记录用户的实时流量并将其用于镜像、负载测试、监控和详细分析。 3.出现背景 随着应用程序的增长,测试它所需的工作量也会呈指数级增长。GoRepl…...
【大模型】RankRAG:基于大模型的上下文排序与检索增强生成的统一框架
文章目录 A 论文出处B 背景B.1 背景介绍B.2 问题提出B.3 创新点 C 模型结构C.1 指令微调阶段C.2 排名与生成的总和指令微调阶段C.3 RankRAG推理:检索-重排-生成 D 实验设计E 个人总结 A 论文出处 论文题目:RankRAG:Unifying Context Ranking…...
高效的后台管理系统——可进行二次开发
随着互联网技术的迅猛发展,企业的数字化管理变得愈加重要。后台管理系统作为数据存储与业务管理的核心,成为了现代企业不可或缺的一部分。今天我们要介绍的是一款名为 若依后台管理框架 的系统,它不仅支持跨平台应用,还能提供丰富…...
