动态规划课堂7-----两个数组的dp问题（等价代换）

news/2024/4/28 1:32:19/文章来源:https://blog.csdn.net/2301_80035594/article/details/136636540

目录

引言：

例题1：最长公共子序列

例题2：不同的子序列

例题3：通配符匹配

例题4：正则表达式

结语：

引言：

本节我们就要进入两个数组的dp问题的学习，通过前面几个章节的学习，相信友友们对动态规划的解题步骤和代码编写步骤已经有了一定的了解(*/ω＼*)，接下来我会通过例题来帮助大家理解两个数组dp问题的一般解题模板，那废话不多说我们开始吧👍👍👍！

首先我先给出这类dp问题的常见的套路和状态表示如下： 

两个数组的dp问题最常用的状态表示就是dp[i][j]表示选取第一个数组的(0,i)区间以及第二个数组(0,j)区间作为研究对象，利用两个表最后一个位置的状况来递推出关系，进而填写dp表。

例题1：最长公共子序列

链接：最长公共子序列

题目简介：

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

  • 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

解法（动态规划）：

 1. 状态表示：

两个数组的动态规划，我们的定义状态表示的经验就是：

（1）选取第⼀个数组[0, i] 区间以及第⼆个数组[0, j] 区间作为研究对象。

（2）结合题目要求，定义状态表示。

在这道题中，我们根据定义状态表示为：dp[i][j] 表示： s1 的[0, i] 区间以及s2 的[0, j] 区间内的所有的子序列中，最长公共子序列的长度。

 2.状态转移方程：

分析状态转移方程的经验就是根据最后⼀个位置的状况，分情况讨论：

（1）两个字符相同， s1[i] = s2[j] ：那么最长公共子序列就在s1 的[0, i - 1] 以及s2 的[0, j - 1] 区间上找到⼀个最长的，然后再加上s1[i]即可。因此dp[i][j] = dp[i - 1][j - 1] + 1 。

（2）两个字符不相同， s1[i] != s2[j] ：那么最长公共子序列⼀定不会同时以s1[i]和s2[j] 结尾。那么我们找最长公共子序列时，有下面三种策略：

1.去s1 的[0, i - 1] 以及s2 的[0, j] 区间内找：此时最大长度为dp[i - 1][j] 。

2.去s1 的[0, i] 以及s2 的[0, j - 1]区间内找：此时最大长度为dp[i ][j - 1]。

3.去s1 的[0, i - 1] 以及s2 的[0, j - 1]区间内找：此时最大长度为dp[i - 1][j - 1] 。

我们要三者的最大值即可。但是我们细细观察会发现，第三种包含在第⼀种和第⼆种情况里面，但是我们求的是最大值，并不影响最终结果。因此只需求前两种情况下的最大值即可。

综上，状态转移方程为：

（1）if(s1[i] == s2[j]) dp[i][j] = dp[i - 1][j - 1] + 1 。

（2）if(s1[i] != s2[j]) dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) 。.

 3.初始化：

当s1 为空时，没有长度，同理s2也是。因此第一行和第⼀列里面的值初始化为0即可保证后续填表是正确的。当为字符串时可以再字符串前面添加一个空字符来对其我们的下标，这样我们就不用注意下标的映射关系了。

 4.填表顺序：

从上往下填写每⼀行，每⼀行从左往右。

 5.返回值：

返回dp[m][n]。

代码如下：

class Solution {public int longestCommonSubsequence(String text1, String text2) {//1.创建 dp 表//2.初始化//3.填表//4.返回值int n = text1.length();int m = text2.length();int[][] dp = new int[n + 1][m + 1];text1 = " " + text1;text2 = " " + text2;for(int i = 1;i <= n;i++){for(int j = 1;j <= m;j++){if(text1.charAt(i) == text2.charAt(j)){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[n][m];}
}

时间复杂度：O（n * m）

空间复杂度：O（n * m）

例题2：不同的子序列

链接：不同的子序列

题目简介：给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。

解法（动态规划）：

这题说是要取模但是实际做不用取模也可以过。

 1. 状态表示：

dp[i][j] 表示：在字符串 s 的 [0, j] 区间内的所有子序列中，有多少个 t 字符串 [0, i] 区间内的子串。（两个数组的dp问题状态表示一般都长这样）。

 2.状态转移方程：

根据最后⼀个位置的元素来进行分类讨论和分析。

（1）当t[i] == s[j]的时候，此时的子序列有两种选择：

1.⼀种选择是：子序列选择s[j]作为结尾，此时相当于在状态dp[i - 1][j - 1]中的所有符合要求的子序列的后面，再加上⼀个字符s[j]（请大家结合状态表示， 好好理解这句话），此时dp[i][j] = dp[i - 1][j - 1]。不用加一，求的是个数不是长度。

2.另⼀种选择是：我就是任性，我就不选择s[j]作为结尾。此时相当于选择了状态dp[i][j - 1] 中所有符合要求的子序列。我们也可以理解为继承了上个状态里面的求得的子序列。此时dp[i][j] = dp[i][j - 1] 。

两种情况加起来，就是 t[i] == s[j]时的结果。

（2）当t[i] != s[j] 的时候，此时的子序列只能从dp[i][j - 1] 中选择所有符合要求的子序列。只能继承上个状态里面求得的子序列， dp[i][j] = dp[i][j - 1] 。

综上所述，状态转移方程为：

（1）所有情况下都可以继承上⼀次的结果： dp[i][j] = dp[i][j - 1].

（2）当 t[i] == s[j]时，可以多选择⼀种情况： dp[i][j] += dp[i - 1][j - 1].

 3.初始化：

辅助节点 + 字符串前面加一个空格，这两种初始化方法一起用。

当s为空时，t的子串中有⼀个空串和它⼀样，因此初始化第⼀行全部为1 。

 4.填表顺序：

从上往下

从左往右

 5.返回值：

返回dp[m][n]的值。

代码如下：

class Solution {public int numDistinct(String s, String t) {//1.创建 dp 表//2.初始化//3.填表//4.返回值//s大m//t小nint n = t.length();int m = s.length();int[][] dp = new int[n + 1][m + 1];s = " " + s;t = " " + t;for(int i = 0;i <= m;i++){dp[0][i] = 1;}for(int i = 1;i <= n;i++){for(int j = i;j <= m;j++){if(t.charAt(i) == s.charAt(j)){dp[i][j] = dp[i - 1][j - 1];}dp[i][j] += dp[i][j - 1];}}return dp[n][m];}
}

时间复杂度：O（n * m）

空间复杂度：O（n * m）

例题3：通配符匹配

链接：通配符匹配

题目简介：

给你一个输入字符串 (s) 和一个字符模式 (p) ，请你实现一个支持 '?' 和 '*' 匹配规则的通配符匹配：

  • '?' 可以匹配任何单个字符。
  • '*' 可以匹配任意字符序列（包括空字符序列）。

判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。

  解法（动态规划）：

 1. 状态表示：

dp[i][j] 表示： p字符串[0, j] 区间内的子串能否匹配字符串s的 [0, i] 区间内的子串。

 2.状态转移方程：

根据最后⼀个位置的元素来分情况讨论：

（1）当s[i] == p[j]或p[j] == '?' 的时候，此时两个字符串匹配上了当前的⼀个字符，只能从dp[i - 1][j - 1] 中看当前字符前面的两个子串是否匹配。只能继承上个状态中的匹配结果，dp[i][j] = dp[i][j - 1] 

（2）当p[j] == '*' 的时候，此时匹配策略有两种选择：

1.⼀种选择是： * 匹配空字符串，此时相当于它匹配了⼀个寂寞，直接继承状态dp[i][j - 1] ，此时dp[i][j] = dp[i][j - 1] 。

2.另⼀种选择是： * 向前匹配1 ~ n 个字符，直至匹配上整个s1串。此时相当于从dp[k][j - 1]所有匹配情况中，选择性继承可以成功的情况。此时dp[i][j] = dp[k][j - 1]。

（3）当p[j] 不是特殊字符，且不与s[i]相等时，无法匹配。

综上所述，状态转移方程为：

（1）当s[i] == p[j] 或p[j] == '?' 时： dp[i][j] = dp[i][j - 1].

（2）当p[j] == '*' 时，有多种情况需要讨论： dp[i][j] = dp[k][j - 1] (0 <= k <= i).

优化：当我们发现，计算⼀个状态的时候，需要⼀个循环才能搞定的时候，我们要想到去优化。优 化的方向就是用⼀个或者两个状态来表示这⼀堆的状态。通常就是把它写下来，然后用数学的方式做一个等价替换。我们惊奇的发现， dp[i][j] 的状态转移方程里面除了第⼀项以外，其余的都可以用dp[i - 1][j]替代。因此，我们优化我们的状态转移方程为： dp[i][j] = dp[i - 1][j] || dp[i][j - 1] 。

 3.初始化：

（1）dp[0][0]表示两个空串能否匹配，答案是显然的，初始化为true。

（2）第一行表示s是⼀个空串， p串和空串只有⼀种匹配可能，即p串表示会为" *** " ，此时也相当于空串匹配上空串。所以，我们可以遍历p串，把所有前导为" * " 的p子串和空串的dp值设为true。

（3）第⼀列表示p是⼀个空串，不可能匹配上s 串，跟随数组初始化即可。

 4.填表顺序：

从上往下填每一行，每一行从左往右。

 5.返回值：

返回dp[m][n]。

对应代码如下：

class Solution {public boolean isMatch(String s, String p) {//1.创建 dp 表//2.初始化//3.填表//4.返回值//s为n//p为mint n = s.length();int m = p.length();boolean[][] dp = new boolean[n + 1][m + 1];s = " " + s;p = " " + p;boolean tmp = true;dp[0][0] = true;for(int i = 1;i <= m;i++){if(p.charAt(i) != '*'){tmp = false;}dp[0][i] = tmp;}for(int i = 1;i <= n;i++){for(int j = 1;j <= m;j++){if(p.charAt(j) == '?'){dp[i][j] = dp[i - 1][j - 1];}else if(p.charAt(j) == '*'){dp[i][j] = dp[i][j - 1] || dp[i - 1][j];}else{dp[i][j] = (s.charAt(i) == p.charAt(j)) && dp[i -1][j - 1];}}}return dp[n][m];}
}

例题4：正则表达式

链接：正则表达式

题目简介：

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

  • '.' 匹配任意单个字符
  • '*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

解法（动态规划）：

 1. 状态表示：

dp[i][j] 表示：字符串p的[0, j]区间和字符串s的[0, i]区间是否可以匹配。

 2.状态转移方程：

（1）当s[i] == p[j] 或p[j] == '.' 的时候，此时两个字符串匹配上了当前的⼀个字符， 只能从dp[i - 1][j - 1] 中看当前字符前面的两个子串是否匹配。只能继承上个状态中的匹配结果， dp[i][j] = dp[i - 1][j - 1]。

（2）当p[j] == '*' 的时候，和上道题稍有不同的是，上道题"*" 本身便可匹配0 ~ n 个字符，但此题是要带着p[j - 1]的字符⼀起，匹配0 ~ n 个和p[j - 1] 相同的字符。此时，匹配策略有两种选择：

1.⼀种选择是： p[j - 1]* 匹配空字符串，此时相当于两个字符串什么都没有匹配，直接继承状态dp[i][j - 2] ，此时dp[i][j] = dp[i][j - 2]。

2.另⼀种选择是： p[j - 1]* 向前匹配1 ~ n 个字符，直至匹配上整个s1串。此时相当于从dp[k][j - 2] 中所有匹配情况中，选择性继承可以成功的情况。此时dp[i][j] = dp[k][j - 2]。

（3）当p[j] 不是特殊字符，且不与s[i]相等时，无法匹配。

综上所述，状态转移方程为：

（1）当s[i] == p[j] 或p[j] == '.' 时： dp[i][j] = dp[i][j - 1].

（2）当p[j] == '*' 时，有多种情况需要讨论： dp[i][j] = dp[i][j - 2] ； dp[i][j] = dp[k][j - 1].

优化和第三题一样也是用等价替换，把后面多种情况归结成一种表达式。

 3.初始化：

第一行表示s 是⼀个空串， p 串和空串只有⼀种匹配可能，即p串全部字符表示为"任⼀字符 + * "，此时也相当于空串匹配上空串。所以，我们可以遍历p串，把所有前导为"任⼀字符+ * " 的p子串和空串的dp值设为true。

for(int i = 2;i <= m;i += 2){if(p.charAt(i) != '*'){break;}dp[0][i] = true;}

 4.填表顺序：

从上往下填每一行，每一行从左往右。

 5.返回值：

 根据状态表示，返回dp[m][n]的值。

代码如下：

class Solution {public boolean isMatch(String s, String p) {//1.创建 dp 表//2.初始化//3.填表//4.返回值//s为n//p为mint n = s.length();int m = p.length();boolean[][] dp = new boolean[n + 1][m + 1];s = " " + s;p = " " + p;for(int i = 2;i <= m;i += 2){if(p.charAt(i) != '*'){break;}dp[0][i] = true;}dp[0][0] = true;for(int i = 1;i <= n;i++){for(int j = 1;j <= m;j++){if(p.charAt(j) != '*'){dp[i][j] = (p.charAt(j) == '.' || p.charAt(j) == s.charAt(i)) && dp[i - 1][j - 1];}else{dp[i][j] = (dp[i][j - 2]) || (p.charAt(j - 1) == s.charAt(i)|| p.charAt(j - 1) == '.') && dp[i - 1][j];}}}return dp[n][m];}
}

结语：

其实写博客不仅仅是为了教大家，同时这也有利于我巩固知识点，和做一个学习的总结，由于作者水平有限，对文章有任何问题还请指出，非常感谢。如果大家有所收获的话还请不要吝啬你们的点赞收藏和关注，这可以激励我写出更加优秀的文章。

                                               

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

如若内容造成侵权/违法违规/事实不符，请联系dt猫网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

终于来了！FastGPT 正式兼容 GPT 应用

终于来了！FastGPT 正式兼容 GPT 应用

终于来了&#xff01;FastGPT 正式兼容 GPT 应用 FastGPT V4.7 正式加入了工具调用功能&#xff0c;可以兼容 GPTs 的 Actions。这意味着&#xff0c;你可以直接导入兼容 GPTs 的 Agent 工具&#xff01; Gapier 是一组无需编码&#xff0c;开箱可用的&#xff0c;并且已经适配…
阅读更多...
快速入门go语言

快速入门go语言

环境搭建 编译器安装 1、编译器下载地址 2、打开命令行模式&#xff0c;输入go version ide安装 ide下载地址 依赖管理 goproxy 1、goproxy代理地址 // 阿里云 https://mirrors.aliyun.com/goproxy // 微软 https://goproxy.io // 七牛 https://goproxy.cn 2、ide配置g…
阅读更多...
蚂蚁庄园今日答案

蚂蚁庄园今日答案

蚂蚁庄园是一款爱心公益游戏&#xff0c;用户可以通过喂养小鸡&#xff0c;产生鸡蛋&#xff0c;并通过捐赠鸡蛋参与公益项目。用户每日完成答题就可以领取鸡饲料&#xff0c;使用鸡饲料喂鸡之后&#xff0c;会可以获得鸡蛋&#xff0c;可以通过鸡蛋来进行爱心捐赠。其中&#…
阅读更多...
UG NX二次开发(C#)-通过曲线组生成NURBS曲面

UG NX二次开发(C#)-通过曲线组生成NURBS曲面

文章目录 1、前言2、UG NX中通过曲线组生成NURBS曲面的操作3、采用NXOpen C#方法的源代码1、前言 在UG NX中，曲线、曲面的操作使用比较多，对于创建NURBS曲面，可以通过曲线组来生成，本文以NXOpen C#的方法实现通过曲线组生成NURBS曲面的功能。对于UG NX二次开发感兴趣或者有…
阅读更多...
windows上打开redis服务闪退问题处理

windows上打开redis服务闪退问题处理

方法1&#xff1a;在windows上面打开redis服务时&#xff0c;弹窗闪退可能是6379端口占用&#xff0c;可以用以下命令查看&#xff1a; netstat -aon | findstr 6379 如果端口被占用可以用这个命令解决&#xff1a; taskkill /f /pid 进程号 方法2&#xff1a; 可以使用…
阅读更多...
力扣热门算法题 112. 路径总和，115. 不同的子序列，120. 三角形最小路径和

力扣热门算法题 112. 路径总和，115. 不同的子序列，120. 三角形最小路径和

112. 路径总和&#xff0c;115. 不同的子序列&#xff0c;120. 三角形最小路径和&#xff0c;每题做详细思路梳理&#xff0c;配套Python&Java双语代码&#xff0c; 2024.03.25 可通过leetcode所有测试用例。 目录 112. 路径总和 解题思路 完整代码 Java Python 115…
阅读更多...
机器学习——元学习

机器学习——元学习

元学习&#xff08;Meta Learning&#xff09;是一种机器学习方法&#xff0c;旨在使模型能够学习如何学习。它涉及到在学习过程中自动化地学习和优化学习算法或模型的能力。元学习的目标是使模型能够从有限的训练样本中快速适应新任务或新环境。 在传统的机器学习中&#xff…
阅读更多...
数据结构算法系列----贪心算法

数据结构算法系列----贪心算法

目录 一、什么是贪心 1、定义&#xff1a; 2、举例&#xff1a; 二、例题 完整代码&#xff1a; 一、什么是贪心 1、定义&#xff1a; 贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法。在贪心算法中&#xff0c;通过 局部最优 解来达到全局最优解。贪心算法…
阅读更多...
Mysql数据库：事务管理

Mysql数据库：事务管理

目录 一、Mysql事务的概述 1、Mysql事务的概念 2、事务的ACID四大特性 3、事务之间的相互影响 4、事务的四种隔离级别 5、MySQL与Oracle自动提交事务的区别 6、事务隔离级别的作用范围 二、Mysql事务相关操作 1、查询和设置事务隔离级别 1.1 全局级事务隔离级别 1.1…
阅读更多...
量子计算+运营优化！IonQ 和 德国DESY 合作提升机场登机口调度效率

量子计算+运营优化！IonQ 和 德国DESY 合作提升机场登机口调度效率

内容来源&#xff1a;量子前哨&#xff08;ID&#xff1a;Qforepost&#xff09; 编辑丨慕一 编译/排版丨 沛贤 深度好文&#xff1a;1200字丨8分钟阅读 3月14日&#xff0c;量子计算公司IonQ宣布了与德国电子同步加速器&#xff08;DESY&#xff0c;德国的大型粒子物理学研…
阅读更多...
【正点原子FreeRTOS学习笔记】————（2）FreeRTOS的任务创建和删除

【正点原子FreeRTOS学习笔记】————（2）FreeRTOS的任务创建和删除

这里写目录标题 一、任务创建和删除的API函数&#xff08;熟悉&#xff09;二、任务创建和删除&#xff08;动态方法&#xff09;&#xff08;掌握&#xff09;三、任务创建和删除&#xff08;静态方法&#xff09;&#xff08;掌握&#xff09; 一、任务创建和删除的API函数&a…
阅读更多...
数据结构：初识树和二叉树

数据结构：初识树和二叉树

目前主流的方式是左孩子右兄弟表示法 我们的文件系统就是一个树 以上就是树的概念&#xff0c;我们今天还要来学习一种从树演变的重要的结构&#xff1a;二叉树 顾名思义二叉树就是一个结点最多有两个子树。 其中我们还要了解满二叉树和完全二叉树的概念 注意我们的完全二叉…
阅读更多...
Java项目：78 springboot学生宿舍管理系统的设计与开发

Java项目：78 springboot学生宿舍管理系统的设计与开发

作者主页&#xff1a;舒克日记 简介&#xff1a;Java领域优质创作者、Java项目、学习资料、技术互助 文中获取源码 项目介绍 系统的角色&#xff1a;管理员、宿管、学生 管理员管理宿管员&#xff0c;管理学生&#xff0c;修改密码&#xff0c;维护个人信息。 宿管员管理公寓…
阅读更多...
微服务高级篇（三）：分布式缓存+Redis集群

微服务高级篇（三）：分布式缓存+Redis集群

文章目录 一、单点Redis的问题及解决方案二、Redis持久化2.1 单机安装Redis2.2 RDB持久化2.3 AOF持久化2.4 RDB和AOF对比 三、Redis主从3.1 搭建Redis主从架构3.1.1 集群结构3.1.2 准备实例和配置3.1.3 启动3.1.4 开启主从关系3.1.5 测试 3.2 数据同步3.2.1 全量同步【建立连接…
阅读更多...
盏燕生物科技将出席2024第七届燕窝天然滋补品博览会

盏燕生物科技将出席2024第七届燕窝天然滋补品博览会

参展企业介绍 深圳市盏燕生物科技有限公司&#xff0c;办公室地址位于中国第一个经济特区&#xff0c;鹏城深圳&#xff0c;深圳市龙岗区平湖街道禾花社区富安大道18号亚钢工贸大楼1栋1017A&#xff0c;我公司主要提供一般经营项目是&#xff1a;初级农产品、海产品、化妆品、…
阅读更多...
批量添加时，两个选择框为一组，不能选择一模一样的值，将不符合条件的值禁止设为禁止点击

批量添加时，两个选择框为一组，不能选择一模一样的值，将不符合条件的值禁止设为禁止点击

效果展示&#xff1a; 完整代码如下&#xff1a; <template><div class"container"><div v-for"item in arr"><el-select v-model"item.name" placeholder"请选择" change"changeBox"><el-opti…
阅读更多...
el-card设置内边距

el-card设置内边距

el-card设置内边距 :deep(.el-card .el-card__body) {padding: 5px; }
阅读更多...
Spring中常用的注解及使用规则

Spring中常用的注解及使用规则

文章目录 前言一、Spring注解是什么&#xff1f;二、使用步骤1.注解使用 总结 前言 提示&#xff1a;这里可以添加本文要记录的大概内容&#xff1a; 在学习Spring中&#xff0c;我们汇经常用到注解来简化我们的工作&#xff0c;接下来将为大家简单介绍一下常用的注解 提示&a…
阅读更多...
如何实现无公网IP及服务器实现公网环境企业微信网页应用开发调试

如何实现无公网IP及服务器实现公网环境企业微信网页应用开发调试

文章目录 1. Windows安装Cpolar2. 创建Cpolar域名3. 创建企业微信应用4. 定义回调本地接口5. 回调和可信域名接口校验6. 设置固定Cpolar域名7. 使用固定域名校验 企业微信开发者在应用的开发测试阶段&#xff0c;应用服务通常是部署在开发环境&#xff0c;在有数据回调的开发场…
阅读更多...
蓝桥杯真题Day40 倒计时19天 纯练题！

蓝桥杯真题Day40 倒计时19天 纯练题！

蓝桥杯第十三届省赛真题-统计子矩阵 题目描述 给定一个 N M 的矩阵 A&#xff0c;请你统计有多少个子矩阵 (最小 1 1&#xff0c;最大 N M) 满足子矩阵中所有数的和不超过给定的整数 K? 输入格式 第一行包含三个整数 N, M 和 K. 之后 N 行每行包含 M 个整数&#xf…
阅读更多...
推荐文章
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站 广利置业