代码随想录算法训练营第五十七天 | 647. 回文子串、516. 最长回文子序列、动态规划总结

647. 回文子串

动规五部曲

1、确定dp数组(dp table)以及下标的含义

在判断字符串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。

 2、确定递推公式

当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++;
        dp[i][j] = true;
    } else if (dp[i + 1][j - 1]) { // 情况三
        result++;
        dp[i][j] = true;
    }
}

3、dp数组如何初始化

dp[i][j]初始化为false。如果为true,则表示已经全部匹配了

4、确定遍历顺序

首先从递推公式中可以看出,情况三是根据dp[i + 1][j - 1]是否为true,在对dp[i][j]进行赋值true的。

dp[i + 1][j - 1] 在 dp[i][j]的左下角,如图:

如果这矩阵是从上到下,从左到右遍历,那么会用到没有计算过的dp[i + 1][j - 1],也就是根据不确定是不是回文的区间[i+1,j-1],来判断了[i,j]是不是回文,那结果一定是不对的。

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

5、举例推导dp数组        

图中有6个true,所以就是有6个回文子串。

注意因为dp[i][j]的定义,所以j一定是大于等于i的,那么在填充dp[i][j]的时候一定是只填充右上半部分

class Solution {
public:
    int countSubstrings(string s) {
        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
        int result = 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) {
                        result++;
                        dp[i][j] = true;
                    } else if (dp[i + 1][j - 1]) {
                        result++;
                        dp[i][j] = true;
                    }
                }
            }
        }
        return result;
    }
};

516. 最长回文子序列

子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。

动规五部曲

1、确定dp数组(dp table)以及下标的含义

dp[i][j]:字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]

2、确定递推公式

如果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]);

 3、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]才不会被初始值覆盖。

4、确定遍历顺序

从递归公式中,可以看出,dp[i][j] 依赖于 dp[i + 1][j - 1] ,dp[i + 1][j] 和 dp[i][j - 1],如图:

所以遍历i的时候一定要从下到上遍历,这样才能保证下一行的数据是经过计算的

 5、举例推导dp数组

输入s:"cbbd" 为例,dp数组状态如图:

红色框即:dp[0][s.size() - 1]; 为最终结果。

 

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
        for (int i = 0; i < s.size(); i++) dp[i][i] = 1;
        //本题采用动态规划遍历顺序,与647. 回文子串题一样
        for (int i = s.size() - 1; i >= 0; i--) {
            for(int j = i + 1; j < s.size(); j++) {
                if (s[i] == s[j]) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
                }
            }
        }
        return dp[0][s.size() - 1];
    }
};

动态规划总结

动态规划这里时刻牢记动规五部曲,鉴于自身没有什么强大思维能力,所以每次写题的时候,慢慢来慢慢思考,动态规划给我的感受算不上难的那种,重点是在动规五部曲中前三步(当然其实没有都很重要),dp数组的定义,可以很好的推导出递推公式,通过递推公式可以方便初始化,然后确定遍历顺序,最后通过例子验证思路的正确性。

在做动规题目时,当我遇到新题的时候,思路不是特别清晰,但是通过看讲解理解了解题思路之后,慢慢的可以写出个大概来,但是细节处理不到位,在确定遍历顺序与初始化的时候时不时的会感到疑惑,这时必须去看题解了,理解题目思路以后,可以在脑中回想一下,或者在纸上模拟。动规不是在短时间内轻松掌握并熟练应用的,如果想达到熟练应用的地步应该每天去看看解过的题目,明白这道题是如何思考的,这类题应该用什么样的思维。

在动规里面给我印象深刻的题目有背包系列问题,股票问题,以及子序列问题,这几类题目平时练得比较多,因此在刷题过程中,即使每天会忘记一些,但是在做过一道题目以后,也能比较轻松解第二道题(大部分时候是能理解第二道题题解),这三个系列的题在leetcode上有比较多的题目供我们练习,可以每天再多看一道题,加深理解(即使不想做新题也可以从旧题出发)。加油!

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

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

相关文章

Motion Planning学习笔记一:配置空间、图、图搜索、图遍历

学习高飞博士的路径规划课程所总结的学习笔记。 目录 1、配置空间&#xff08;Configuration Space, C-space&#xff09; 2、图&#xff08;Graphs&#xff09; 3、图搜索&#xff08;Graph Search Basis&#xff09; 3.1、总体框架 3.2、两种基本的图遍历算法 3.3、启…

【Python】【进阶篇】十七、Python爬虫实现实时翻译

目录十七、Python爬虫实现实时翻译17.1 JS代码slat与sign17.2 Python代码表示参数17.3 完整程序实现十七、Python爬虫实现实时翻译 YD翻译是以异步方式实现数据加载的&#xff0c;要实现数据抓取&#xff0c;其过程极其繁琐。 上一节《Python爬虫的浏览器实现抓包》&#xff…

【hello Linux】Linux开发工具

目录 1. vim&#xff1a;文本编辑器 1.1 各种模式的切换 补充&#xff1a;ctrl r命令 1.2 命令模式的操作 1.3 插入模式的操作 1.4 底行模式的操作 1.5 配置vim环境 1.6 配置亲属关系 2. gcc/g&#xff1a;编译器 2.1 预处理&#xff1a; 2.2 编译&#xff1a; 2.3 汇编&#x…

如何利用ChatGPT辅助优化刷题性能

根据土著刷题共建群里的一个小伙伴反馈&#xff0c;刷题会出现切题卡顿的情况&#xff0c;有时会出现滑不动的情况。 定位问题 为了定位切题卡顿问题的具体原因&#xff0c;测试了高低端手机&#x1f4f1;、切换2G、3G、4G低网络状态等各种影响切题的现实情况&#xff0c;经过借…

STM32F4_定时器精讲(TIM)

目录 1. 什么是定时器&#xff1f; 2. STM32定时器简介 2.1 高级控制定时器 TIM1和TIM8 2.1.1 TIM1和TIM8简介 2.1.2 时基单元 2.1.3 计数器模式 2.1.4 重复计数器 2.1.5 时钟选择 2.1.6 捕获/比较通道 2.1.7 输入捕获模式 2.1.8 其他功能 2.2 通用定时器 TIM2到TI…

Mysql 你还在一个字段一个索引吗

今天看到某系统的mysql在某时段存在thread_running线程数飙高触发告警&#xff0c;挤时间分析了该异常时间段的慢日志记录&#xff0c;并进行了sql优化 慢日志记录主要归为3个慢sql (编号1&#xff0c;2&#xff0c;3) 一、 1号sql原文 select * from feeds where topics_id &…

【MySQL数据库原理】MySQL Community安装与配置

目录 安装成功之后查看版本验证1、介绍、安装与配置数据库2、操作MySQL数据库3、MySQL数据库原理安装成功之后查看版本验证 SELECT VERSION();查看mysql版本号 1、介绍、安装与配置数据库 下载安装包:https://download.csdn.net/download/weixin_41194129/87672588 MySQL…

Visual studio C#中通过nuget安装sqlite库及C#中sliqte的用法

以前在Visual studio 的2017版中讲过如何使用sqlite&#xff0c;这里我们再次说说如何使用sqlite&#xff0c;以前Nuget使用还不是很流行很普及&#xff0c;大多数人不知道&#xff0c;但随着VS的升级&#xff0c;Nuget成为安装插件或者引用库文件标准的获取手段&#xff0c;所…

Qt Quick - TabBar

Qt Quick - TabBar使用总结一、概述二、调整选项卡三、Flickable标签三、定制化一、概述 TabBar其实就是选项卡&#xff0c;TabBar是由TabButton控件填充&#xff0c;TabBar可以与任何提供currentIndex属性的布局或容器控件一起使用&#xff0c;如StackLayout或SwipeView。Tab…

Vector - CAPL - CAN x 总线信息获取

在CAN&CANFD测试中&#xff0c;我们经常需要获取到CAN总线的负载、错误帧、过载帧、发送错误等等CAN总线上面的信息&#xff0c;这些信息如此重要&#xff0c;但是如果真的要写代码去实现也是相当不易的&#xff0c;那我们该如何去获取到的呢&#xff1f;下面我们就来一起看…

Object方法

私人博客 许小墨のBlog —— 菜鸡博客直通车 系列文章完整版&#xff0c;配图更多&#xff0c;CSDN博文图片需要手动上传&#xff0c;因此文章配图较少&#xff0c;看不懂的可以去菜鸡博客参考一下配图&#xff01; 系列文章目录 前端系列文章——传送门 JavaScript系列文章—…

柔性数组【结构体和动态内存的结合】

全文目录前言柔性数组的定义语法柔性数组的特点柔性数组的使用柔性数组的优势前言 很多人可能没有听过柔性数组这个概念&#xff0c;但是在C99中柔性数组是确实存在的。我个人感觉有点像动态内存和结构体的结合。 柔性数组的定义语法 结构中的最后一个元素允许是未知大小的数…

NumPy 秘籍中文第二版:三、掌握常用函数

原文&#xff1a;NumPy Cookbook - Second Edition 协议&#xff1a;CC BY-NC-SA 4.0 译者&#xff1a;飞龙 在本章中&#xff0c;我们将介绍许多常用函数&#xff1a; sqrt()&#xff0c;log()&#xff0c;arange()&#xff0c;astype()和sum()ceil()&#xff0c;modf()&…

《Java8实战》第1章 Java 8、9、10 以及 11 的变化

如想了解 Oracle 公司对 JDK 的最新支持情况&#xff0c;请访问https://www.oracle.com/technetwork/java/java-se-supportroadmap.html。所有的示例代码均可见于图灵社区本书主页 http://ituring.com.cn/book/2659“随书下载”处。 1.1 为什么要关心 Java 的变化 Java8做的…

[MAUI 项目实战] 手势控制音乐播放器(三): 动画

文章目录吸附动画确定位置平移动画回弹动画使用自定义缓动函数多重动画点击动画项目地址上一章节我们创建了手势容器控件PanContainer&#xff0c;它对拖拽物进行包装并响应了平移手势和点击手势。拖拽物现在虽然可以响应手势操作&#xff0c;但视觉效果较生硬&#xff0c;一个…

总结一下Redis的缓存雪崩、缓存击穿、缓存穿透

缓存是提高系统性能的一种常见手段&#xff0c;其中Redis是一种常用的高性能缓存数据库。但是在使用缓存时&#xff0c;可能会遇到一些问题&#xff0c;比如缓存击穿、缓存穿透、缓存雪崩等问题&#xff0c;本文将介绍这些问题的概念、原因以及解决方案。 缓存击穿 缓存击穿指…

SQL Server 连接查询和子查询

提示&#xff1a; 利用单表简单查询和多表高级查询技能&#xff0c;并且根据查询要求灵活使用内连接查询、外连接查询或子查询等。同时还利用内连接查询的两种格式、三种外连接查询语法格式和子查询的语法格式。 文章目录前言1.查询所有学生的学号、姓名、选修课程号和成绩方法…

Vue学习——【第四弹】

前言 上一篇文章 Vue学习——【第三弹】 中我们了解了MVVM模型&#xff0c;这篇文章接着学习Vue中的数据代理。 简单介绍 数据代理就是**一个对象(A)来代理对另一个对象(B)的属性操作(A一定要包含B)。**直接看定义大家可能觉得有些抽象&#xff0c;我们可以用代码来实现。 …

全景丨0基础学习VR全景制作,后期篇:嵌入视频前期注意事项及后期处理

大家好&#xff0c;欢迎观看蛙色官方系列全景摄影课程&#xff01; 一、前期拍摄要点 嵌入视频的简介和用途 livepano即完全无缝融合到全景图中的热点嵌入视频。 这种无缝融合是真正无缝&#xff0c;从而让观者产生沉浸感和真实感。例如在场景中放入宠物、让喷泉动起来、灯光…

MPAM中PARTID的虚拟化(Virtualization)

MPAM支持对PARTID的virtualization&#xff0c;需要在满足所有以下条件下才能使用&#xff1a; 在当前的security状态下有实现EL2&#xff1b;支持MPAM virtualization&#xff0c;也就是MPAMIDR_EL1.HAS_HCR等于1&#xff1b; 以下是MPAM中使用virtual-to-physical PARTID ma…
最新文章