代码随想录 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.安全生产资金保障制度建立后关键在于落实,各施工企业在落实安全生…...
8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂
蛋白质结合剂(如抗体、抑制肽)在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上,高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术,但这类方法普遍面临资源消耗巨大、研发周期冗长…...
UDP(Echoserver)
网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法:netstat [选项] 功能:查看网络状态 常用选项: n 拒绝显示别名&#…...
Module Federation 和 Native Federation 的比较
前言 Module Federation 是 Webpack 5 引入的微前端架构方案,允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...
稳定币的深度剖析与展望
一、引言 在当今数字化浪潮席卷全球的时代,加密货币作为一种新兴的金融现象,正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而,加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下,稳定…...
LOOI机器人的技术实现解析:从手势识别到边缘检测
LOOI机器人作为一款创新的AI硬件产品,通过将智能手机转变为具有情感交互能力的桌面机器人,展示了前沿AI技术与传统硬件设计的完美结合。作为AI与玩具领域的专家,我将全面解析LOOI的技术实现架构,特别是其手势识别、物体识别和环境…...
前端中slice和splic的区别
1. slice slice 用于从数组中提取一部分元素,返回一个新的数组。 特点: 不修改原数组:slice 不会改变原数组,而是返回一个新的数组。提取数组的部分:slice 会根据指定的开始索引和结束索引提取数组的一部分。不包含…...
DBLP数据库是什么?
DBLP(Digital Bibliography & Library Project)Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高,数据库文献更新速度很快,很好地反映了国际计算机科学学术研…...
规则与人性的天平——由高考迟到事件引发的思考
当那位身着校服的考生在考场关闭1分钟后狂奔而至,他涨红的脸上写满绝望。铁门内秒针划过的弧度,成为改变人生的残酷抛物线。家长声嘶力竭的哀求与考务人员机械的"这是规定",构成当代中国教育最尖锐的隐喻。 一、刚性规则的必要性 …...
从零手写Java版本的LSM Tree (一):LSM Tree 概述
🔥 推荐一个高质量的Java LSM Tree开源项目! https://github.com/brianxiadong/java-lsm-tree java-lsm-tree 是一个从零实现的Log-Structured Merge Tree,专为高并发写入场景设计。 核心亮点: ⚡ 极致性能:写入速度超…...
精益数据分析(98/126):电商转化率优化与网站性能的底层逻辑
精益数据分析(98/126):电商转化率优化与网站性能的底层逻辑 在电子商务领域,转化率与网站性能是决定商业成败的核心指标。今天,我们将深入解析不同类型电商平台的转化率基准,探讨页面加载速度对用户行为的…...
