代码随想录算法训练营第五十五天【动态规划part15】 | 392.判断子序列、115.不同的子序列

本文主要是介绍代码随想录算法训练营第五十五天【动态规划part15】 | 392.判断子序列、115.不同的子序列,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

392.判断子序列

题目链接

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

求解思路

也可以用双指针来做。

动规五部曲

1.确定dp数组及其下标含义

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

关于为什么是定义下标i-1和j-1,参看dp数组的初始化

2.确定递推公式

if (s[i - 1] == t[j - 1]),那么dp[i][j] = dp[i - 1][j - 1] + 1,因为找到了一个相同的字符,相同子序列长度自然要在dp[i-1][j-1]的基础上加1

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];

3.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二维矩阵中可以留出初始化的区间,如图

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

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

4.确定遍历顺序

dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1],那么遍历顺序也应该是从上到下,从左到右

5.举例推导dp数组

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

p[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。

代码

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

115.不同的子序列

题目链接

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

求解思路

动规五部曲

1.确定dp数组及其下表含义

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

2.确定递推公式

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

  • 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]。

3.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][0] 表示以i-1为结尾的s可以随便删除元素,出现空字符串的个数,那么dp[i][0]一定都是1。

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

最后一个特殊位置,dp[0][0]应该是1,空字符串s,可以删除0个元素,变成空字符串t。

4.确定遍历顺序

从上到下,从左到右

5.举例推导dp数组

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

代码

class Solution {
public:int numDistinct(string s, string t) {vector<vector<uint64_t>> dp(s.size()+1, vector<uint64_t>(t.size()+1));for (int i = 0; i < s.size(); i++) dp[i][0] = 1;for (int j = 1; j < t.size(); j++) dp[0][j] = 0;for (int i = 1; i <= s.size(); i++){for (int j = 1; j <= t.size(); 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[s.size()][t.size()];}
};

这篇关于代码随想录算法训练营第五十五天【动态规划part15】 | 392.判断子序列、115.不同的子序列的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/454707

相关文章

利用Python调试串口的示例代码

《利用Python调试串口的示例代码》在嵌入式开发、物联网设备调试过程中,串口通信是最基础的调试手段本文将带你用Python+ttkbootstrap打造一款高颜值、多功能的串口调试助手,需要的可以了... 目录概述:为什么需要专业的串口调试工具项目架构设计1.1 技术栈选型1.2 关键类说明1.3 线程模

SpringBoot基于配置实现短信服务策略的动态切换

《SpringBoot基于配置实现短信服务策略的动态切换》这篇文章主要为大家详细介绍了SpringBoot在接入多个短信服务商(如阿里云、腾讯云、华为云)后,如何根据配置或环境切换使用不同的服务商,需... 目录目标功能示例配置(application.yml)配置类绑定短信发送策略接口示例:阿里云 & 腾

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

Python如何精准判断某个进程是否在运行

《Python如何精准判断某个进程是否在运行》这篇文章主要为大家详细介绍了Python如何精准判断某个进程是否在运行,本文为大家整理了3种方法并进行了对比,有需要的小伙伴可以跟随小编一起学习一下... 目录一、为什么需要判断进程是否存在二、方法1:用psutil库(推荐)三、方法2:用os.system调用

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

Python实现特殊字符判断并去掉非字母和数字的特殊字符

《Python实现特殊字符判断并去掉非字母和数字的特殊字符》在Python中,可以通过多种方法来判断字符串中是否包含非字母、数字的特殊字符,并将这些特殊字符去掉,本文为大家整理了一些常用的,希望对大家... 目录1. 使用正则表达式判断字符串中是否包含特殊字符去掉字符串中的特殊字符2. 使用 str.isa

Java使用SLF4J记录不同级别日志的示例详解

《Java使用SLF4J记录不同级别日志的示例详解》SLF4J是一个简单的日志门面,它允许在运行时选择不同的日志实现,这篇文章主要为大家详细介绍了如何使用SLF4J记录不同级别日志,感兴趣的可以了解下... 目录一、SLF4J简介二、添加依赖三、配置Logback四、记录不同级别的日志五、总结一、SLF4J

使用Java将DOCX文档解析为Markdown文档的代码实现

《使用Java将DOCX文档解析为Markdown文档的代码实现》在现代文档处理中,Markdown(MD)因其简洁的语法和良好的可读性,逐渐成为开发者、技术写作者和内容创作者的首选格式,然而,许多文... 目录引言1. 工具和库介绍2. 安装依赖库3. 使用Apache POI解析DOCX文档4. 将解析

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

Python中判断对象是否为空的方法

《Python中判断对象是否为空的方法》在Python开发中,判断对象是否为“空”是高频操作,但看似简单的需求却暗藏玄机,从None到空容器,从零值到自定义对象的“假值”状态,不同场景下的“空”需要精... 目录一、python中的“空”值体系二、精准判定方法对比三、常见误区解析四、进阶处理技巧五、性能优化