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

这篇具有很好参考价值的文章主要介绍了动态规划课堂7-----两个数组的dp问题(等价代换)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

引言:

例题1:最长公共子序列

例题2:不同的子序列

例题3:通配符匹配

例题4:正则表达式

结语:


引言:

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

动态规划课堂7-----两个数组的dp问题(等价代换),动态规划,动态规划,算法,java,leetcode,DP

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

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

动态规划课堂7-----两个数组的dp问题(等价代换),动态规划,动态规划,算法,java,leetcode,DP

例题1:最长公共子序列

链接:最长公共子序列

题目简介:

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

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

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

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

动态规划课堂7-----两个数组的dp问题(等价代换),动态规划,动态规划,算法,java,leetcode,DP

解法(动态规划):

 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]) 。.

动态规划课堂7-----两个数组的dp问题(等价代换),动态规划,动态规划,算法,java,leetcode,DP

 3.初始化:

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

动态规划课堂7-----两个数组的dp问题(等价代换),动态规划,动态规划,算法,java,leetcode,DP

 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 取模。动态规划课堂7-----两个数组的dp问题(等价代换),动态规划,动态规划,算法,java,leetcode,DP

解法(动态规划):

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

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

动态规划课堂7-----两个数组的dp问题(等价代换),动态规划,动态规划,算法,java,leetcode,DP

 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) ,请你实现一个支持 '?' 和 '*' 匹配规则的通配符匹配:

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

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

动态规划课堂7-----两个数组的dp问题(等价代换),动态规划,动态规划,算法,java,leetcode,DP

  解法(动态规划):

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

动态规划课堂7-----两个数组的dp问题(等价代换),动态规划,动态规划,算法,java,leetcode,DP

 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的,而不是部分字符串。

动态规划课堂7-----两个数组的dp问题(等价代换),动态规划,动态规划,算法,java,leetcode,DP

解法(动态规划):

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

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

动态规划课堂7-----两个数组的dp问题(等价代换),动态规划,动态规划,算法,java,leetcode,DP

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

    }
}

结语:

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

                                               动态规划课堂7-----两个数组的dp问题(等价代换),动态规划,动态规划,算法,java,leetcode,DP文章来源地址https://www.toymoban.com/news/detail-842377.html

到了这里,关于动态规划课堂7-----两个数组的dp问题(等价代换)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【动态规划】两个数组问题

    题目链接 状态表示 dp[i][j] 表示 s1 0 到 i 区间内,以及时s2 0 到 j 区间内所有的子序列中,最长的公共子序列 状态转移方程 根据最后一个位置的请款分类讨论。 初始化 关于字符串的dp问题,空串是有研究意义的。引入空串的概念之后会方便我们的初始化 这里还可以使用之前

    2024年02月11日
    浏览(34)
  • 动态规划课堂4-----子数组系列

    目录 引入: 例题1:最大子数组和 例题2:环形子数组的最大和 例题3:乘积最大子数组 例题4:乘积为正数的最长子数组 总结: 结语: 在动态规划(DP)子数组系列中,我们还是用前面几节所用的 解题思路1. 状态表示,2.状态转移方程,3.初始化,4.填表顺序,5.返回值 。在

    2024年03月11日
    浏览(35)
  • 从01背包开始动态规划:暴力解法 + dp + 滚动数组 + dp优化

        01背包问题是动态规划中最经典的问题之一,本篇将通过给出其四种解法,使读者更深刻理解动态规划。   有N件物品和一个容量是 V 的背包,每个物品有各自的体积和价值,且每个物品只能放一次(这也是01背包名字的由来),如何让背包里装入的物品具有最大的价值总

    2024年04月17日
    浏览(53)
  • 动态规划课堂5-----子序列问题(动态规划 + 哈希表)

    目录 引言: 例题1:最长递增子序列 例题2:最长定差子序列 例题3:最长的斐波那契子序列的长度 例题4:最长等差数列 例题5:等差数列划分II-子序列 结语: 要想解决子序列问题那么就要理解子序列和子数组的区别,二者的定义如下。 子序列: 是由数组派生而来的序列,

    2024年03月13日
    浏览(64)
  • 动态规划课堂6-----回文串问题

    目录 引言: 例题1:回文子串 例题2:回文串分割IV 例题3:分割回文串II 例题4:最长回文子序列 例题5:让字符串成为回文串的最小插入次数 回文字符串  是正着读和倒过来读一样的字符串。 动态规划的回文串问题一般是把 子串 是否是回文串的信息保持在dp表里面,所以更

    2024年03月18日
    浏览(46)
  • 【动态规划 区间dp 位运算】100259. 划分数组得到最小的值之和

    动态规划 区间dp 位运算 给你两个数组 nums 和 andValues,长度分别为 n 和 m。 数组的 值 等于该数组的 最后一个 元素。 你需要将 nums 划分为 m 个 不相交的连续 子数组,对于第 ith 个子数组 [li, ri],子数组元素的按位AND运算结果等于 andValues[i],换句话说,对所有的 1 = i = m,n

    2024年04月15日
    浏览(31)
  • 【动态规划】NK刷题之DP7 连续子数组的最大乘积

    ❤️博客主页: 小镇敲码人 🍏 欢迎关注:👍点赞 👂🏽留言 😍收藏 🌞在一切变好之前,我们总要经历一些不开心的日子,这段日子也许很长,也许只是一觉醒来。有时候,选择快乐,更需要勇气。 🍉 如果你也迷失在了路上,对人生充满了迷惘,不要害怕,冷静下来,

    2024年02月08日
    浏览(48)
  • 两个数组的动态规划——最长公共子序列模型

    1.考虑空串,即dp表多出一行一列, 代表某个字符串为空。 2.考虑最后一个位置;是否相等; 3.可在字符串最前面加虚拟位置以对应映射关系; 4.一般横行是j,列是i。此时第一行代表第二个字符串不为空,即第一个字符串是空的 给你两个字符串  s   和  t  ,统计并返回在

    2024年03月10日
    浏览(65)
  • 【LeetCode: 2369. 检查数组是否存在有效划分 | 暴力递归=>记忆化搜索=>动态规划 | 线性dp】

    🚀 算法题 🚀 🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀 🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨ 🌲 作者简介:硕风和炜,CSDN-Java领域新星创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文

    2023年04月19日
    浏览(56)
  • 【动态规划】NK刷题记之DP8乘积为正数的最长连续子数组

    ❤️博客主页: 小镇敲码人 🍏 欢迎关注:👍点赞 👂🏽留言 😍收藏 🌞在一切变好之前,我们总要经历一些不开心的日子,这段日子也许很长,也许只是一觉醒来。有时候,选择快乐,更需要勇气。 🍉 如果你也迷失在了路上,对人生充满了迷惘,不要害怕,冷静下来,

    2024年02月09日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包