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

目录

引言:

例题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小n
        int 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为m
        int 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为m
        int 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];

    }
}

结语:

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

                                               

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

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

相关文章

深入剖析JavaScript引擎的工作原理

文章目录 导文什么是JavaScript引擎的工作原理&#xff1f;1. 解析阶段解析器&#xff08;Parser&#xff09; 2. 编译阶段3. 执行阶段解释器&#xff08;Interpreter&#xff09;优化器&#xff08;Optimizer&#xff09; 4. 垃圾回收阶段垃圾回收器 其他 导文 JavaScript引擎…

如何用SCSS制作小铃铛振动/震动/摇晃/晃动的特效/效果?

放大了看效果 ​​​​​​​​​​​​​​ // 摇晃小铃铛振动/震动/摇晃/晃动的特效/效果---------------------------------------- [sg-shaking] {display: inline-block;transform-origin: center top;animation: sg-shaking 1s alternate forwards; }keyframes sg-shaki…

【Apache ShenYu源码】如何实现负载均衡模块设计

ShenYu是一个异步的&#xff0c;高性能的&#xff0c;跨语言的&#xff0c;响应式的 API 网关。有关ShenYu的介绍可以戳这。 一、前瞻 今天我们尝试不同的代码阅读方式&#xff0c;按模块来去阅读源码&#xff0c;看看效果如何。 本次阅读锁定在shenyu-loadbalancer&#xf…

Java安全 反序列化(3) CC1链-TransformedMap版

Java安全 反序列化(3) CC1链-TransformedMap版 本文尝试从CC1的挖掘思路出发&#xff0c;理解CC1的实现原理 文章目录 Java安全 反序列化(3) CC1链-TransformedMap版配置jdk版本和源代码配置前记 为什么可以利用一.CC链中的命令执行我们可以尝试一下通过InvokerTransformer.tr…

Windows环境下编译ffmpeg 6.1源码--Virtual Studio + Msys2方式

环境准备 约定&#xff1a;源码全部放到sources下&#xff0c;目录结构说明 /d/java/ffmpeg #工程工目录 ├── build #存放编译文件的目录&#xff0c;子目录为具体模块的构建目录 │ ├── fdk-aac │ ├── ffmpeg │ └── x264 ├── instal…

O2OA(翱途)开发平台前端安全配置建议(一)

O2OA开发平台是一个集成了多种功能的开发环境&#xff0c;前端安全在其中显得尤为重要。前端是用户与平台交互的直接界面&#xff0c;任何安全漏洞都可能被恶意用户利用&#xff0c;导致用户数据泄露、非法操作或系统被攻击。因此&#xff0c;前端安全是确保整个系统安全的第一…

B011-springcloud alibaba rpc通信 Dubbo

目录 介绍实现提供统一业务api服务提供者1.导入依赖2添加dubbo配置3编写并暴露服务 服务消费者1.导入依赖2添加dubbo配置3引用服务 测试 介绍 Dubbo是阿里巴巴开源的基于 Java 的高性能 RPC分布式服务框架&#xff0c;致力于提供高性能和透明化的 RPC远程服务调用方案&#xf…

数学建模(Topsis python代码 案例)

目录 介绍&#xff1a; 模板&#xff1a; 案例&#xff1a; 极小型指标转化为极大型&#xff08;正向化&#xff09;&#xff1a; 中间型指标转为极大型&#xff08;正向化&#xff09;&#xff1a; 区间型指标转为极大型&#xff08;正向化&#xff09;&#xff1a; 标…

【图像分类】基于深度学习的人脸表情识别(8种表情,ResNet网络)

写在前面: 首先感谢兄弟们的关注和订阅,让我有创作的动力,在创作过程我会尽最大能力,保证作品的质量,如果有问题,可以私信我,让我们携手共进,共创辉煌。(专栏订阅用户订阅专栏后免费提供数据集和源码一份,超级VIP用户不在服务范围之内,不想订阅专栏的兄弟们可以私信…

“洞见·智领未来——2024行业开局暨成渝(内江)服务外包产业发展大会”共商服务外包新未来新业态

3月19日-20日&#xff0c;由中国信息协会、中共内江市委、内江市人民政府指导&#xff0c;中国信息协会数字经济专委会、中共内江市东兴区委、内江市东兴区人民政府共同主办&#xff0c;鸿联九五集团、首席客户官百人会&#xff08;CCO100&#xff09;承办的“洞见 智领未来—…

【Git】第一课:Git的介绍

简介 什么是Git? Git是一个开源的分布式版本控制系统&#xff0c;用于跟踪代码的改变和协同开发。它最初由Linus Torvalds为了管理Linux内核开发而创建&#xff0c;现已成为开源软件开发中最流行的版本控制系统&#xff0c;没有之一。Git允许多人同时在不同的分支上工作&…

opencv各个模块介绍(1)

Core 模块&#xff1a;核心模块&#xff0c;提供了基本的数据结构和功能。 常用的核心函数&#xff1a; cv::Mat&#xff1a;表示多维数组的数据结构&#xff0c;是OpenCV中最常用的类之一&#xff0c;用于存储图像数据和进行矩阵运算。 cv::Scalar&#xff1a;用于表示多通道…

mac下Appuim环境安装-持续更新中

参考资料 Mac安装Appium_mac电脑安装appium-CSDN博客 安卓测试工具&#xff1a;Appium 环境安装&#xff08;mac版本&#xff09;_安卓自动化测试mac环境搭建-CSDN博客 1. 基本环境依赖 1 node.js 2 JDK&#xff08;Java JDK&#xff09; 3 Android SDK 4 Appium&#x…

51单片机学习9 串口通讯

51单片机学习9 串口通讯 一、串口通讯简介UARTSTC89C51RC/RD的串口资源 二、51单片机串口介绍1. 内部结构2. 寄存器&#xff08;1&#xff09;串口控制寄存器SCON&#xff08;2&#xff09;电源控制寄存器PCON 3. 计算波特率4. 串口配置步骤 三、 开发示例1. 硬件电路2. 代码实…

好用的GPTs:指定主题搜索、爬虫、数据清洗、数据分析自动化

好用的GPTs&#xff1a;指定主题搜索、爬虫、数据清洗、数据分析自动化 Scholar&#xff1a;搜索 YOLO小目标医学方面最新论文Scraper&#xff1a;爬虫自动化数据清洗数据分析 点击 Explore GPTs&#xff1a; Scholar&#xff1a;搜索 YOLO小目标医学方面最新论文 搜索 Scho…

超过 1200 个能够拦截在野外检测到的 2FA 的网络钓鱼工具包

超过 1200 个能够拦截在野外检测到的 2FA 的网络钓鱼工具包。 #################### 免责声明&#xff1a;工具本身并无好坏&#xff0c;希望大家以遵守《网络安全法》相关法律为前提来使用该工具&#xff0c;支持研究学习&#xff0c;切勿用于非法犯罪活动&#xff0c;对于恶…

【计算机】——51单片机

单片机是一种内部包含CPU、存储器和输入/输出接口等电路的集成电路&#xff08;IC芯片&#xff09; 单片机是单片微型计算机&#xff08;Single Chip Microcomputer&#xff09;的简称&#xff0c;用于控制领域&#xff0c;所以又称为微型控制器&#xff08;Microcontroller U…

Eureka的介绍和作用,以及搭建

一、Eureka的介绍和作用 Eureka是Netflix开源的一种服务发现和注册工具&#xff0c;它为分布式系统中的服务提供了可靠的服务发现和故障转移能力。Eureka是Netflix的微服务架构的关键组件之一&#xff0c;它能够实时地监测和管理服务实例的状态和可用性。 在Eureka架构中&…

学成在线_视频处理_视频转码不成功

问题 当我们用xxljob进行视频处理中的转码操作时会发现视频转码不成功。即程序会进入下图所示的if语句内。 问题原因 在进行视频转码时程序会调用Mp4VideoUtil类下的 generateMp4方法&#xff0c;而result接收的正是该方法的返回值。那么什么时候generateMp4方法的返回值会…

SQLiteC/C++接口详细介绍sqlite3_stmt类(七)

返回&#xff1a;SQLite—系列文章目录 上一篇&#xff1a;SQLiteC/C接口详细介绍sqlite3_stmt类&#xff08;六&#xff09; 下一篇&#xff1a; 无 22、sqlite3_column_database_name 用于返回结果集中指定列的数据库名称。如果结果集是由多个Join操作产生的&#xff0c;…