代码随想录算法训练营第五十四天丨 动态规划part15

392.判断子序列

思路

(这道题也可以用双指针的思路来实现,时间复杂度也是O(n))

这道题应该算是编辑距离的入门题目,因为从题意中我们也可以发现,只需要计算删除的情况,不用考虑增加和替换的情况。

所以掌握本题的动态规划解法是对后面要讲解的编辑距离的题目打下基础

动态规划五部曲分析如下:

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

dp[i][j] 表示以下标i-1为结尾的字符串s,和以下标j-1为结尾的字符串t,相同子序列的长度为dp[i][j]

注意这里是判断s是否为t的子序列。即t的长度是大于等于s的。

为啥要表示下标i-1为结尾的字符串呢,为啥不表示下标i为结尾的字符串呢?

为什么这么定义卡哥在 718. 最长重复子数组 (opens new window)中做了详细的讲解。

其实用i来表示也可以!

但我统一以下标i-1为结尾的字符串来计算,这样在下面的递归公式中会容易理解一些,如果还有疑惑,可以继续往下看。

  • 确定递推公式

在确定递推公式的时候,首先要考虑如下两种操作,整理如下:

  • if (s[i - 1] == t[j - 1])
    • t中找到了一个字符在s中也出现了
  • if (s[i - 1] != t[j - 1])
    • 相当于t要删除元素,继续匹配

if (s[i - 1] == t[j - 1]),那么dp[i][j] = dp[i - 1][j - 1] + 1;,因为找到了一个相同的字符,相同子序列长度自然要在dp[i-1][j-1]的基础上加1(如果不理解,在回看一下dp[i][j]的定义

if (s[i - 1] != t[j - 1]),此时相当于t要删除元素,t如果把当前元素t[j - 1]删除,那么dp[i][j] 的数值就是 看s[i - 1]与 t[j - 2]的比较结果了,即:dp[i][j] = dp[i][j - 1];

其实这里 大家可以发现和 1143.最长公共子序列 (opens new window)的递推公式基本那就是一样的,区别就是 本题 如果删元素一定是字符串t,而 1143.最长公共子序列 是两个字符串都可以删元素。

  • dp数组如何初始化

从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1],所以dp[0][0]和dp[i][0]是一定要初始化的。

这里大家已经可以发现,在定义dp[i][j]含义的时候为什么要表示以下标i-1为结尾的字符串s,和以下标j-1为结尾的字符串t,相同子序列的长度为dp[i][j]

因为这样的定义在dp二维矩阵中可以留出初始化的区间,如图:

392.判断子序列

如果要是定义的dp[i][j]是以下标i为结尾的字符串s和以下标j为结尾的字符串t,初始化就比较麻烦了。

dp[i][0] 表示以下标i-1为结尾的字符串,与空字符串的相同子序列长度,所以为0. dp[0][j]同理。

int[][] dp = new int[t.length()+1][s.length()+1];
  • 确定遍历顺序

同理从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1],那么遍历顺序也应该是从上到下,从左到右

如图所示:

392.判断子序列1

  • 举例推导dp数组

以示例一为例,输入:s = "abc", t = "ahbgdc",dp状态转移图如下:

392.判断子序列2

dp[i][j]表示以下标i-1为结尾的字符串s和以下标j-1为结尾的字符串t 相同子序列的长度,所以如果dp[s.size()][t.size()] 与 字符串s的长度相同说明:s与t的最长相同子序列就是s,那么s 就是 t 的子序列。

图中dp[s.size()][t.size()] = 3, 而s.size() 也为3。所以s是t 的子序列,返回true。

动规五部曲分析完毕,C++代码如下:

class Solution {
    public boolean isSubsequence(String s, String t) {
        int[][] dp = new int[t.length()+1][s.length()+1];
        for (int i = 1; i <= t.length(); i++) {

            for (int j = 1; j <= s.length(); j++) {
                if (s.charAt(j-1) == t.charAt(i-1)){
                    dp[i][j] = dp[i-1][j-1]+1;
                }else {
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[t.length()][s.length()] == s.length() ? true : false;
    }
}
  • 时间复杂度:O(n × m)
  • 空间复杂度:O(n × m)

115.不同的子序列

思路

这道题目如果不是子序列,而是要求连续序列的,那就可以考虑用KMP。

这道题目相对于72. 编辑距离,简单了不少,因为本题相当于只有删除操作,不用考虑替换增加之类的。

但相对于刚讲过的动态规划:392.判断子序列 (opens new window)就有难度了,这道题目双指针法可就做不了了,来看看动规五部曲分析如下:

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

dp[i][j]:以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。

为什么i-1,j-1 这么定义卡哥在 718. 最长重复子数组 (opens new window)中做了详细的讲解。

  • 确定递推公式

这一类问题,基本是要分析两种情况

  • s[i - 1] 与 t[j - 1]相等
  • s[i - 1] 与 t[j - 1] 不相等

当s[i - 1] 与 t[j - 1]相等时,dp[i][j]可以有两部分组成。

一部分是用s[i - 1]来匹配,那么个数为dp[i - 1][j - 1]。即不需要考虑当前s子串和t子串的最后一位字母,所以只需要 dp[i-1][j-1]。

一部分是不用s[i - 1]来匹配,个数为dp[i - 1][j]。

这里可能有录友不明白了,为什么还要考虑 不用s[i - 1]来匹配,都相同了指定要匹配啊

例如: s:bagg 和 t:bag ,s[3] 和 t[2]是相同的,但是字符串s也可以不用s[3]来匹配,即用s[0]s[1]s[2]组成的bag。

当然也可以用s[3]来匹配,即:s[0]s[1]s[3]组成的bag。

所以当s[i - 1] 与 t[j - 1]相等时,dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];

当s[i - 1] 与 t[j - 1]不相等时,dp[i][j]只有一部分组成,不用s[i - 1]来匹配(就是模拟在s中删除这个元素),即:dp[i - 1][j]

所以递推公式为:dp[i][j] = dp[i - 1][j];

这里可能有录友还疑惑,为什么只考虑 “不用s[i - 1]来匹配” 这种情况, 不考虑 “不用t[j - 1]来匹配” 的情况呢。

这里大家要明确,我们求的是 s 中有多少个 t,而不是 求t中有多少个s,所以只考虑 s中删除元素的情况,即 不用s[i - 1]来匹配 的情况。

  • dp数组如何初始化

从递推公式dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; 和 dp[i][j] = dp[i - 1][j]; 中可以看出dp[i][j] 是从上方和左上方推导而来,如图:,那么 dp[i][0] 和dp[0][j]是一定要初始化的。

每次当初始化的时候,都要回顾一下dp[i][j]的定义,不要凭感觉初始化。

dp[i][0]表示什么呢?

dp[i][0] 表示:以i-1为结尾的s可以随便删除元素,出现空字符串的个数。

那么dp[i][0]一定都是1,因为也就是把以i-1为结尾的s,删除所有元素,出现空字符串的个数就是1。

再来看dp[0][j],dp[0][j]:空字符串s可以随便删除元素,出现以j-1为结尾的字符串t的个数。

那么dp[0][j]一定都是0,s如论如何也变成不了t。

最后就要看一个特殊位置了,即:dp[0][0] 应该是多少。

dp[0][0]应该是1,空字符串s,可以删除0个元素,变成空字符串t。

初始化分析完毕,代码如下:

int[][] dp = new int[s.length() + 1][t.length() + 1];
for (int i = 0; i < s.length(); i++) {
    dp[i][0] = 1;
}
  • 确定遍历顺序

从递推公式dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; 和 dp[i][j] = dp[i - 1][j]; 中可以看出dp[i][j]都是根据左上方和正上方推出来的。

所以遍历的时候一定是从上到下,从左到右,这样保证dp[i][j]可以根据之前计算出来的数值进行计算。

代码如下:

 for (int i = 1; i <= s.length(); i++) {
     for (int j = 1; j <= t.length(); j++) {
         if (s.charAt(i - 1) == t.charAt(j - 1)) {
             dp[i][j] = dp[i - 1][j - 1] + dp[i-1][j];
         }else {
             dp[i][j] = dp[i-1][j];
         }
     }
 }
  • 举例推导dp数组

以s:"baegg",t:"bag"为例,推导dp数组状态如下:

115.不同的子序列

如果写出来的代码怎么改都通过不了,不妨把dp数组打印出来,看一看,是不是这样的。

动规五部曲分析完毕,代码如下:

class Solution {
    public int numDistinct(String s, String t) {
        int[][] dp = new int[s.length() + 1][t.length() + 1];

        for (int i = 0; i < s.length(); i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 1; j <= t.length(); j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i-1][j];
                }else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[s.length()][t.length()];
    }
}
  • 时间复杂度: O(n * m)
  • 空间复杂度: O(n * m)

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

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

相关文章

Android Termux安装MySQL,通过内网穿透实现公网远程访问

&#x1f525;博客主页&#xff1a; 小羊失眠啦. &#x1f516;系列专栏&#xff1a; C语言、Linux、Cpolar ❤️感谢大家点赞&#x1f44d;收藏⭐评论✍️ 文章目录 前言1.安装MariaDB2.安装cpolar内网穿透工具3. 创建安全隧道映射mysql4. 公网远程连接5. 固定远程连接地址 前…

互联网+智慧河道大数据一体化管理平台解决方案:PPT43页,附下载

关键词&#xff1a;售前方案工程师&#xff0c;解决方案工程师&#xff0c;技术转售前&#xff0c;技术转售前的优势&#xff0c;软件工程师转售前 一、智慧水务大数据一体化建设背景 1、当前我国供水管网迅速扩张&#xff0c;管理压力加大&#xff0c;供水管网漏损率比较高&…

2023年中国超声波治疗仪发展趋势分析:中高端市场国产化率将稳步上升[图]

超声波治疗机是运用超声波治疗疾病的医用设备。主要由电源&#xff0c;高频振荡电路、超声波能治疗头组成。治疗时应正确掌握超声输出强度、治疗时间和选择不同的工作方式。目前超声波技术在医疗方面的独特疗效已得到医学界的普遍认可&#xff0c;且受到了越来越多临床重视和采…

不允许你还不了解指针的那些事(二)(从入门到精通看这一篇就够了)(数组传参的本质+冒泡排序+数组指针+指针数组)

目录 数组名的理解 使用指针访问数组 一维数组传参的本质 冒泡排序 二级指针 指针数组 指针数组模拟二维数组 字符指针变量 数组指针变量 二维数组传参的本质 函数指针变量 函数指针变量的创建 函数指针变量的使用 两段有趣的代码 代码一 代码二 typedef关键字 函数指针数组 …

反向运算放大器

在学习模拟电路的时候&#xff0c;学习到运算放大器&#xff0c;但实际印象并不深刻&#xff0c;在此进行二次知识整理&#xff0c;以加深深度&#xff0c;下面是我个人对该器件的理解&#xff0c;其他知识暂时不深究&#xff0c;只说一下怎么用。 1、反向运算放大器干什么的&…

有能一键批量转换,轻松将PDF、图片转为Word/Excel的软件吗?

随着数字化时代的到来&#xff0c;OCR技术在我们的生活中变得越来越重要。无论是从图片中提取文字&#xff0c;还是将PDF、图片格式的文件转换为Word或Excel格式&#xff0c;OCR软件都能够为我们提供极大的便利。然而&#xff0c;市面上的OCR软件种类繁多&#xff0c;哪一款软件…

obsidian和bookmaster

1 手动安装插件 插件地址&#xff1a;https://forum-zh.obsidian.md/t/topic/12333 安装file服务器 地址&#xff1a;http://www.rejetto.com/hfs/ hfs.exe可以改个端口 改成8866&#xff0c;ip地址也可以改成 127.0.0.1 # 因为安装到本地 如果要创建账户的话&#xff0c;就…

Google codelab WebGPU入门教程源码<7> - 完整的元胞自动机之生命游戏的完整实现(源码)

对应的教程文章: https://codelabs.developers.google.com/your-first-webgpu-app?hlzh-cn#7 对应的源码执行效果: 对应的教程源码: 此处源码和教程本身提供的部分代码可能存在一点差异。 class Color4 {r: number;g: number;b: number;a: number;constructor(pr 1.0, …

小白也想写综述(一)

前言 在选择科研方向时&#xff0c;考虑自己的兴趣和职业目标是非常重要的&#xff1a; 综述论文的价值&#xff1a;撰写综述论文&#xff0c;尤其是在深度强化学习和区块链这样的前沿技术领域&#xff0c;能够帮助建立扎实的理论基础&#xff0c;并且对整个领域有一个全面的认…

【科技素养】蓝桥杯STEMA 科技素养组模拟练习试卷4

单选题 1、Soda is sold in packs of 6、12 and 24 cans.What is the minimum number of packs needed to buy exactly 90cans of soda? A、4 B、5 C、6 D、8 答案&#xff1a;B 2、蓝桥杯STEMA考试中心发送有同样内容、重量、体积的试卷&#xff0c;从北京10箱和上海6箱…

Reflect 对象的创建目的

目录 前言 逻辑Reflect对象的创建目的包括&#xff1a; 代码示例 使用 Reflect 操作属性 使用 Reflect 检查属性是否存在 使用 Reflect 创建代理 用法 Reflect对象的用法包括&#xff1a; 用于读取和设置对象属性的方法&#xff1a;Reflect.get(obj, prop)、Reflect.s…

等级保护建设全流程

等保&#xff0c;全称为信息安全等级保护&#xff0c;是对信息和信息载体按照重要性等级分级进行保护的一种工作。 企业的信息系统有收集、储存用户信息的&#xff0c;都需要进行等保建设&#xff0c;以此来整改提升系统的安全防护能力&#xff0c;降低被攻击的风险。若不然一旦…

通付盾Web3专题 | KYT/AML:Web3合规展业的必要条件

与传统证券一样&#xff0c;基于区块链技术发展出来的虚拟资产交易所经历了快速发展而缺乏有效监管的行业早期。除了科技光环加持的各种区块链项目方、造富神话之外&#xff0c;交易所遭到黑客攻击、内部偷窃作恶、甚至经营主体异常而致使投资人血本无归的案例亦令人触目惊心。…

PostgreSQL技术大讲堂 - 第34讲:调优工具pgBagder部署

PostgreSQL从小白到专家&#xff0c;是从入门逐渐能力提升的一个系列教程&#xff0c;内容包括对PG基础的认知、包括安装使用、包括角色权限、包括维护管理、、等内容&#xff0c;希望对热爱PG、学习PG的同学们有帮助&#xff0c;欢迎持续关注CUUG PG技术大讲堂。 第34讲&#…

Consumer的负载均衡

想要提高Consumer的处理速度&#xff0c;可以启动多个Consumer并发处理&#xff0c;这个时候就涉及如何在多个Consumer之间负载均衡的问题&#xff0c;接下来结合源码分析Consumer的负载均衡实现。 要做负载均衡&#xff0c;必须知道一些全局信息&#xff0c;也就是一个Consum…

Accelerate 0.24.0文档 四:Megatron-LM

参考《Megatron-LM》 文章目录 一、Megatron-LM集成简介二、环境配置设置conda环境的步骤&#xff1a; 二、Accelerate Megatron-LM Plugin三、自定义训练过程四、检查点转换五、文本生成六、支持ROPE 、 ALiBi和Multi-Query Attention七、注意事项 一、Megatron-LM集成简介 在…

SystemVerilog学习(8)——包的使用

目录 一、包的定义 二、导出包的内容 1、可以通过域的索引符::号直接引用 2、可以指定索引一些需要的包中定义的类型到指定的容器中 3、通过通配符*来将包中所有的类别导入到指定容器中 三、包的使用 在进行本文的学习之前&#xff0c;首先需要对SV中类相关的内容有充分的认识…

mount /dev/mapper/centos-root on sysroot failed处理

今天发现centos7重启开不进去系统 通过查看日志主要告警如下 修复挂载目录 xfs_repair /dev/mapper/centos-root不行加-L参数 xfs_repair -L /dev/mapper/centos-root重启 reboot

2023年中国开式冷却塔应用现状及行业市场规模前景分析[图]

开式塔是目前应用最广、类型最多的一种冷却系统。循环水移走工艺介质或换热设备所散发的热量后成为热水&#xff0c;热水进入冷却塔后和空气直接接触&#xff0c;大部分热水得到冷却后&#xff0c;再循环使用。开式冷却塔又可以分为逆流式冷却塔和横流式冷却塔&#xff0c;按照…

基于Vue+SpringBoot的海南旅游景点推荐系统 开源项目

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 用户端2.2 管理员端 三、系统展示四、核心代码4.1 随机景点推荐4.2 景点评价4.3 协同推荐算法4.4 网站登录4.5 查询景点美食 五、免责说明 一、摘要 1.1 项目介绍 基于VueSpringBootMySQL的海南旅游推荐系统&#xff…