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

进阶理解:leetcode115.不同的子序列(细节深度)

这道题是困难题,本章是针对于动态规划解决,对于思路进行一个全面透彻的讲解,但是并不是对于基础讲解思路,而是渗透到递推式和dp填数的详解,如果有读者不清楚基本的解题思路,请看我的这篇文章算法训练营DAY53|392.判断子序列、115.不同的子序列-CSDN博客

但在看的过程中,你可能会有为什么把dp数组设为以i-1和j-1的下标这样的奇怪含义的困惑,这是为了方便初始化,不用对每一个位置进行一开始的判定初始化,也就是说可能要对于一开始下标匹配做一些多余的处理,详细的解释可以翻看我往期作品,其中会有更为详细的介绍,本期文章,我主要是针对,对于思路有一些了解,但是对于题解本身仍存有一些疑惑的读者准备的。

当然也是对于 我之前写的那期题解未能写的清楚的一些部分的补充。


这里还要纠正一下第一次写那个题解的一部分话是存在一些问题的,两个字符匹配的第一项并不是未匹配成功的结果,如果读者不能明白我在说什么直接看下面的代码即可,不必要去看那期文章,以避免误导读者。

class Solution {
public:int numDistinct(string s, string t) {int m=s.size(),n=t.size();vector<vector<uint64_t>>dp(m+1,vector<uint64_t>(n+1,0));for(int i=0;i<=m;++i)dp[i][0]=1;for(int i=1;i<=m;++i){for(int j=1;j<=n;++j){if(s[i-1]==t[j-1])dp[i][j]=dp[i-1][j-1]+dp[i-1][j];else dp[i][j]=dp[i-1][j];}}return dp[m][n];}
};

如上是题目正确的代码,可以ac。

首先我们来分析的是递推式,然后是初始化和打表,最后是整体的总结。

先粘上一张代码随想录的图片,当大家需要看图对比时候可以回过头开看:

请注意:子序列问题中dp解决时,通常在需要在两个数组或字符串中找答案时候,大多数情况下都需要开辟二维dp数组来解决问题。
明确递推式dp【i】【j】代表以i-1和j-1结尾的字符串s和t,当前情况下,s字符串中t出现的个数有多少个。
递推公式:当i-1和j-1位置上的s和t字符串对应下标字符相等,则当前位置可由dp【i-1】【j-1】推出来,这个递推式的意思是由于这两个字符相等所以不用管该两个字符,
然后去看相当于i-2和j-2对应的位置下,s中包含了多少个t。
你也可以理解为当前的dp【i】【j】要填数,就要看上一个状态时,也就是dp【i-1】【j-1】的状态,因为此时对应下标的元素相等,所以直接去看上一个状态,而此时不需要删除元素
那上一个状态dp【i-1】【j-1】有没有可能需要删除元素呢?当然有可能,但这并不是我们本次填数需要解决的问题,上一个状态肯定在上一个状态被解决了。
为什么不是dp【i-1】【j-1】+1?当前字符相等应该意味着我们又多匹配成功了一个字符,所以理应+1啊
看这两个【bag】和【bag】当该填数dp【2】【2】时候,我们根据dp数组定义实际上看的是s的i-1下标,和t的j-1下标位置
那么也就是此时正在比较【ba】和【ba】呢,它的上一个状态是【b】【b】虽然匹配是相等,但是这并不意味着我们只要匹配相等字符就得+1
因为这道题求的不是重复字符最多有多少个!!!
那怎么完成匹配成功t字符串时候加入答案呢?因为有第二项递推式!
是dp【i-1】【j】这个递推式就相当于不回退当前的t字符串的匹配下标,而是回退s字符串下标,看看此时状态是否有s中有t字符串的这种情况
举例:【bagg】和【bag】这两个,那么除了s字符中的s[0]s[1]s[3]可以得到t字符串,s[0]s[1]s[2]这个组合也可以得到t字符串。
所以这正是我们可以回退s的原因,换个角度去看,这也是我们匹配t这个字符串的整个字符串的方法。把这两个递推式相加就可以得到dp【i】【j】了
我们不考虑t字符串回退的原因,在这里是因为我们是在s字符串里找有多少个t,而不是在t里找,所以应该回退s里的字符。如果你选择回退t此时对应的下标,那么将不可能得到正确答案,因为无论最后s能不能
从中找到t字符串的完整序列,只要t中的部分子数组在s中出现过,那么它一直沿用前面的状态,那是不是肯定会得到1次匹配?
你想想t一直沿用前面的状态,而最开始的状态是s有字符而t无字符,所以一定会有一解。这得出的答案一定是错误的。
所以t不可回退字符,t只能向前匹配,这样保证了求到最后的是s里是否包含完整的t字符串,而不是只要包含一部分子数组就可以完成匹配。
还有一件事是:s字符下标每次增大1然后重新对t字符串进行匹配,也就解决了以各个的s下标位置为截止,能匹配到最大匹配个数是多少。将它们加起来就是答案。


而如果此时两字符对应不等怎么办
dp【i】【j】=dp【i-1】【j】这里的递推式你可以理解为,删除s字符串当前遍历的字符(模拟删除)而转为用该下标的前一个位置看看有没有
s中含有t的时候,延续那时候的状态就可以了。


初始化也很重要它是得到答案的关键初始化dp数组,s和t数组都为空时候对应dp应该为1,解释:两字符串都为空,则s字符串里包含1个t
当s字符串有内容,t为空,那么s各个状态都为1,解释:s字符串删除全部字符得到空字符串也就是t
当s没内容,t有内容,则这些状态都为0,解释:s无论如何也无法推出t
当两字符串内容不相等时候,也就是s中不包含t那么无论如何也推不出一个,因为s里要想能找到t,那么必须t中的第一个元素与s中的某位置元素发生了起始匹配。
这时初始化产生作用,虽然这种中间某处得到的匹配,匹配不上原始的dp【0】【0】但是它能匹配上dp【i】【0】使得累计1次匹配。
然后接下来的匹配,就是对t字符串各个字符都必须连续匹配,才可以使这个1继承下来,因为递推式的缘故,往后匹配,dp【0】【0】肯定匹配不上
而如果中间某字符没匹配上断档了,那么再匹配上的时候,dp【i-1】【j】也不可能借用到dp【i】【0】就使得最终答案是0。


打表特殊测试用例  s=【bag】t=【bag】
dp[0][0]=1dp[0][1]=0dp[0][2]=0dp[0][3]=0
dp[1][0]=1dp[1][1]=1dp[1][2]=0dp[1][3]=0
dp[2][0]=1dp[2][1]=1dp[2][2]=1dp[2][3]=0
dp[3][0]=1dp[3][1]=1dp[3][2]=1dp[3][3]=1
可见即使中间遍历时候也有完全匹配时候【ba】【ba】但是这并不会使dp【2】【2】变成2
由头上的图片可以知道其实dp【i-1】【j-1】和dp【i-1】【j】都有可能是答案的组成部分
打表bac和bad
dp[0][0]=1dp[0][1]=0dp[0][2]=0dp[0][3]=0
dp[1][0]=1dp[1][1]=1dp[1][2]=0dp[1][3]=0
dp[2][0]=1dp[2][1]=1dp[2][2]=1dp[2][3]=0
dp[3][0]=1dp[3][1]=1dp[3][2]=1dp[3][3]=0

再写该题时候,写到循环部分的时候,想的是t字符串既然不能使之回退,那么是不是应该写成t循环在外面,s循环在里面,这样只循环了一次t,就保证了不回退的效果,而不是写成s循环在外面t循环在内部
但后来发现不是这么一回事,这样写循环是有原因的,它遍历s的各个字符给t去进行匹配,以获得所有的组合答案。如果t循环写外面了,t确实没有回退,但是这样写的思路不就成了拿t的各个元素去找
t里面是否存在s字符串了吗?这不就写反了吗?
还有就是外层for是s内层for是t,并不是没有实现t的禁止回退,所谓t字符串不能回退不是指t的字符串不能重复遍历,不能回退体现在递推公式上,不要弄混淆。
再细说一下具体的匹配机理,是如何实现s拿一个个字符串然后去匹配t的。
首先s字符串每次增大一个匹配范围(表面上看),然后t字符串在s每次增大匹配范围时,重新遍历t字符串去和s的现在范围去匹配,看看现在的s范围能否找到更多的匹配次数并填到dp数组内。
从代码的实际运行角度,s的每次增大一个字符的范围,t重新匹配,并不是匹配0——i,而是拿t的整个字符串去和i这个元素单单去匹配,而非s子串和t字符串匹配。
这实际上无形之中提升了效率,那么怎么实现匹配的正确呢?
递推式已经给出了,如果当前元素匹配不上,那么当前位置填数继承上一次匹配,也就是当前两个字符不匹配,那么相当于放弃当前两个字符的匹配机会,而是选用上一次的对应截止字符处,去继承那一次的
匹配成果。这次的继承是就是回退s而不回退t
如果匹配成功,有两个方向推出,一个是不考虑当前两个字符,因为两个字符当前匹配成功,所以暂时不考虑,但是还没完,还要考虑s往前回退一个字符的情况与t进行匹配的成果,将二者相加得到答案
为什么不回退第二个字符串t我们上面已经说得很清楚了,而回退s为上一个字符是为什么呢?就是因为bag和bagg的测试用例这类情况,也即是说可能存在上一个s的字符也存在匹配的关系,那有人要问
如果是bag和baggg呢?你怎么匹配?这是一样的,第二次的g会继承第一次g匹配成果,而第三次又会继承第二次.看递推式就能知道,两字符匹配成功,答案是左上角数加上头上的数,
而这个头上的数,自然把上一层的g加过来了。
还有一个问题是为什么总是能得到正确答案,我们上面已经说了一些了,但是个人觉得还不够透彻。再说一次
首先它为什么不是每匹配成功一次都+1我们上面说的很清了,当两个字符相等时候的填数再说一下
我们由于初始化的缘故,使得若此时匹配的两个字符匹配不相等,也就是说假如bagg和bag,s字符串bagg匹配到最后一个字符时候,但是t字符串从头开始匹配,这个时候我们由于第二递推式,匹配不等时候会拿
dp【i】【j-1】的数做继承,直到匹配成功填数的时候,真正的递推作用才开始显现
匹配相等时,会把头上的位置也就是dp【i-1】【j】和dp【i-1】【j-1】累加起来,换句话说只有两个字符最后发生匹配时候,才能够获得答案,如果不发生匹配不会获得答案。
这是为什么呢?不是说不匹配会继承前位置吗?但是你要注意,只有同列才能继承,也就是说如果你的上一行列没有做事,那么你不能享受成果,这就相当于祖上得有财富积累,你才能躺平拿到成果,否则你只能
依赖于本身的才能,也就是进入第一递推式,虽然祖上可能没有成果,但你可以收获你左上角人的成果。
所以并不会发生一处匹配成功,全部人都受益的结果。
你左上的成果相当于叔辈的成果,你没有能力时候它不会贡献成果给你享用,只有你的亲祖先才能共享成果,所以如果前面出现多次匹配,也就是说祖先和叔辈都得到了匹配,或他们继承它们的祖先和叔辈匹配
而且同时你也有能力匹配,才会同时得到两方面的匹配成果。
这个左上角匹配也并非与你完全无关,它有数字代表了发生连续匹配。
badgbacg打表
dp[0][0]=1dp[0][1]=0dp[0][2]=0dp[0][3]=0dp[0][4]=0
dp[1][0]=1dp[1][1]=1dp[1][2]=0dp[1][3]=0dp[1][4]=0
dp[2][0]=1dp[2][1]=1dp[2][2]=1dp[2][3]=0dp[2][4]=0
dp[3][0]=1dp[3][1]=1dp[3][2]=1dp[3][3]=0dp[3][4]=0
dp[4][0]=1dp[4][1]=1dp[4][2]=1dp[4][3]=0dp[4][4]=0
这下应该明白了吧,虽然祖上有成果的某些中间量会继承祖上的成果,但这并不一定影响最后的答案,该样例中即使最后一次发生了g和g的匹配,但是它的左上角没有成果也就是出现了断档,而且它的祖上也没有
成果,所以它依然无法收获结果。
这也就是说只要中间断档发生了一次,那么就不再可能延续的上,想尝试的读者可写一个badgh和bacgh试一下打表
简而言之:
对于当前两字符匹配成功,则需要收获结果,结果的第一部分代表了之前字符的连续匹配,第二部分代表了s中存在多个t的继承匹配个数
对于匹配不成功,继承连续匹配结果,这一举动主要是为了下一次的s扩大后的匹配受益,因为s当前字符不可能与t所有字符匹配,那么只要有一次完成了匹配,则这一列的所有位置理应继承那次匹配成功的成果。
以应对下一次循环匹配的时候,对于连续字符匹配的连贯性。
 


相信如果读者事先具备了代码思路,知道题解如何解答,再看这篇文章一定会受益匪浅。

这是对于细节上问题的一些补充。本章就到这里。

都看到这里了如果对您有用的话别忘了一键三连哦,如果是互粉回访我也会做的!

大家有什么想看的题解,或者想看的算法专栏、数据结构专栏,可以去看看往期的文章,有想看的新题目或者专栏也可以评论区写出来,讨论一番,本账号将持续更新。
期待您的关注

相关文章:

进阶理解:leetcode115.不同的子序列(细节深度)

这道题是困难题&#xff0c;本章是针对于动态规划解决&#xff0c;对于思路进行一个全面透彻的讲解&#xff0c;但是并不是对于基础讲解思路&#xff0c;而是渗透到递推式和dp填数的详解&#xff0c;如果有读者不清楚基本的解题思路&#xff0c;请看我的这篇文章算法训练营DAY5…...

数据结构-哈希表(C语言)

哈希表的概念 哈希表就是&#xff1a; “将记录的存储位置与它的关键字之间建立一个对应关系&#xff0c;使每个关键字和一个唯一的存储位置对 应。” 哈希表又称&#xff1a;“散列法”、“杂凑法”、“关键字&#xff1a;地址法”。 哈希表思想 基本思想是在关键字和存…...

HCIA-综合实验(三)

综合实验&#xff08;三&#xff09; 1 实验拓扑2 IP 规划3 实验需求一、福州思博网络规划如下&#xff1a;二、上海思博网络规划如下&#xff1a;三、福州思博与上海思博网络互联四、网络优化 4 配置思路4.1 福州思博配置在 SW1、SW2、SW3 上配置交换网络SW1、SW2、SW3 运行 S…...

Java程序员的成长路径

熟悉JAVA语言基础语法。 学习JAVA基础知识&#xff0c;推荐阅读书单中的经典书籍。 理解并掌握面向对象的特性&#xff0c;比如继承&#xff0c;多态&#xff0c;覆盖&#xff0c;重载等含义&#xff0c;并正确运用。 熟悉SDK中常见类和API的使用&#xff0c;比如&#xff1…...

几种常用的排序

int[] arr new int[]{1, 2,8, 7, 5};这是提前准备好的数组 冒泡排序 public static void bubbleSort(int[] arr) {int len arr.length;for (int i 0; i < len - 1; i) {for (int j 0; j < len - i - 1; j) {if (arr[j] > arr[j1]) {int temp arr[j];arr[j] ar…...

性能测试【第三篇】Jmeter的使用

线程数:10 ,设置10个并发 Ramp-Up时间(秒):所有线程在多少时间内启动,如果设置5,那么每秒启动2个线程 循环次数:请求的重复次数,如果勾选"永远"将一直发送请求 持续时间时间:设置场景运行的时间 启动延迟:设置场景延迟启动时间 响应断言 响应断言模式匹配规则 包括…...

业务:业务系统检查项参考

名录明细云平台摸底1.原有云平台体系&#xff1a;VMware、openstack、ovirt、k8s、docker、混合云系列及版本 2.原有云平台规模&#xff0c;物理机数量、虚拟机数量、迁移业务系统所占配额 3.待补充系统摸底 (适用于物理主机)每一台虚拟机或物理机&#xff1a; 1.系统全局参数…...

解决公网下,k8s calico master节点无法访问node节点创建的pod

目的&#xff1a;解决pod部署成功后&#xff0c;只能在node节点访问&#xff0c;而master节点无法访问 原因&#xff1a;集群搭建时&#xff0c;没有配置公网进行kubectl操作&#xff0c;从而导致系统默认node节点&#xff0c;使用内网IP加入k8s集群&#xff01;如下&#xff…...

六边形架构

Alistair Cockburn是于1953年出生在美国的一位软件开发方法学家。他毕业于康奈尔大学计算机科学专业&#xff0c;并获得了博士学位。 Cockburn在敏捷软件开发领域做出了许多重要的贡献&#xff0c;他被广泛认可为敏捷方法学的奠基人之一。他提出了许多关于敏捷开发的原则和实践…...

基于单片机的智能家居安保系统(论文+源码)

1.系统设计 本次基于单片机的智能家居安保系统设计&#xff0c;在功能上如下&#xff1a; 1&#xff09;以51单片机为系统控制核心&#xff1b; 2&#xff09;温度传感器、人体红外静释电、烟雾传感器来实现检测目的&#xff1b; 3&#xff09;以GSM模块辅以按键来实现远/近程…...

盘点3种Python网络爬虫过程中的中文乱码的处理方法

网络爬虫过程中三种中文乱码的处理方案&#xff0c;希望对大家的学习有所帮助 一、思路 其实解决问题的关键点就是在于一点&#xff0c;就是将乱码的部分进行处理&#xff0c;而处理的方案主要可以从两个方面进行出发。其一是针对整体网页进行提前编码&#xff0c;其二是针对…...

小程序富文本图片大小问题

文章目录 概要uniapp小程序情况解决方法及完整示例 概要 在小程序使用富文本或者在nuiapp&#xff08;小程序的&#xff09;使用富文本都会转为 <rich-text nodes"<p class"p class">内容</p>”></rich-text>如果是这种情况的话在css…...

Diagrams——制作短小精悍的流程图

今天为大家分享的是一款轻量级的流程图绘制软件——Diagrams。 以特定的图形符号加上说明&#xff0c;表示算法的图&#xff0c;称为流程图或框图。流程图是流经一个系统的信息流、观点流或部件流的图形代表。我们常用流程图来说明某一过程。 流程图使用一些标准符号代表某些类…...

Elasticsearch基础条件查询

条件查询 query&#xff1a;查询 match&#xff1a;匹配 match_all&#xff1a;匹配所有 #第一种 GET /shopping/_search?q名字:张三#第二种 GET /shopping/_search {"query": {"match": {"名字": "张三"}} }#全量查询 match_all G…...

【SAP-ABAP】SAP与外围系统对接方式

SAP作为接受方 1.JAVA直接配置IP、账号、密码&#xff08;有些人叫SAPWEBAPI&#xff09;调用SAP里面的RFC函数 2.SAP发布RFC函数&#xff0c;配置webservice地址 3.SAP发布ODATA服务 4.SAP发布restful的http服务 5.我不太懂的UI5和FIORI本质好像也是odata服务 6.IDOC SA…...

云计算的发展趋势

云计算的发展一直是一个极具活力和创新的领域。随着技术的不断进步和应用场景的拓展&#xff0c;云计算将在未来继续发挥重要作用。以下是云计算发展的一些趋势&#xff1a; 边缘计算的崛起&#xff1a; 随着物联网设备的普及和应用场景的增多&#xff0c;边缘计算成为一个重要…...

国民技术Cortex-M0系列单片机IAP升级

考虑到设备部署到现场后有可能需要进行软件升级&#xff0c;之前做过PIC系列单片机的升级&#xff0c;现在想做个国民技术N32G031系列Cortex-M0内核的单片机IAP方案。 因为国民技术系列单片机在很多大程度上都模仿了STM32&#xff0c;所以我想其升级方案极有可能差不多。于是在…...

Pycharm中添加Python库指南

一、介绍 Pycharm是一款为Python开发者提供的集成开发环境&#xff08;IDE&#xff09;&#xff0c;支持执行、调试Python代码&#xff0c;并提供了许多有用的工具和功能&#xff0c;其中之一就是在Pycharm中添加Python库。 添加Python库有许多好处&#xff0c;比如能够增加开…...

Oracle OCP / MySQL OCP认证容易通过吗

诸多学员在首次考OCP时&#xff0c;不清楚要如何选择。在本文中&#xff0c;我会为大家进行讲解&#xff01; 选择OCP认证时需要考虑的几大项目&#xff1a; 授课老师师资经验 课程大纲 试听课程 考试通过率 业界口碑 服务质量 郭一军老师的OCP培训在业界培训的学员中已…...

flutter web 中嵌入一个html

介绍 flutter web 支持使用 HtmlElementView嵌入html import dart:html; import dart:ui as ui; import package:flutter/cupertino.dart;class WebWidget extends StatelessWidget {const WebWidget({super.key});overrideWidget build(BuildContext context) {DivElement fr…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...