算法系列--两个数组的dp问题(1)(下)

简介: 算法系列--两个数组的dp问题(1)

算法系列--两个数组的dp问题(1)(上)

https://developer.aliyun.com/article/1480818?spm=a2c6h.13148508.setting.1.5f4e4f0eex1sKA

💕"低头要有勇气,抬头要有底气。"💕

作者:Mylvzi

文章主要内容:算法系列–两个数组的dp问题(1)

大家好,今天为大家带来的是算法系列--两个数组的dp问题(1),两个数组的dp问题在动态规划问题中属于较难的部分,状态转移方程不易推导,希望大家通过下面的几道题目能够掌握

3.不同的⼦序列

链接:

https://leetcode.cn/problems/distinct-subsequences/submissions/516072259/

分析:

对于两个字符串,公共序列xxxx之类的问题,我们用经验来作为状态表示,本题的状态表示:

  • dp[i][j]:表示s字符串[0,j]区间内包含多少个t字符串[0,i]区间的字符

首先,这个状态表示能返回最终的结果么?可以的,走到最后,就表示s整个字符串内包含多少个t字符串,刚好和题目要求相同

接着分析状态转移方程,对于本题状态转移方程还是有所不同的,首先由于是在s中找有多少个t这样的要求,那么t一定是较小的那个,对于t字符串来说,每次推导状态,都必须包含i位置的字符,注意不是找有多少个公共序列,而是找s中包含多少个t

状态转移方程的推导一般都是根据最后一个状态进行划分,对于t来说,其状态是固定的,不用考虑,对于s来说需要分类讨论,因为包不包含最后一个位置的字符是对整个状态有影响的,所以可以分为以下两种情况

  • 包含s[j]:也就是s字符串的子序列必须以j位置的字符结尾,那么此时dp[i][j]的生效就有条件了,必须t[i] == s[j],dp[i][j]才能生效,且dp[i][j] = dp[i - 1][j - 1]
  • 不包含 s[j]:在s字符串的[0,i-1]区间内找t字符串[0,i]出现的次数

初始化

还是根据经验,二维的dp一般选择增加一行一列的方式来规避越界,第一行表示i == 0,即t字符串为空串,所以第一行全部初始化为1,第一列表示j == 0,即s字符串为空串,第一行全部初始化为0

返回值

易得返回dp[m][n]

代码:

class Solution {
    public int numDistinct(String s, String t) {
        // 特殊判断
        if(t.length() > s.length()) return 0;
        // 创建dp表并初始化
        int m = t.length();
        int n = s.length();
        int[][] dp = new int[m + 1][n + 1];
        for(int j = 0; j <= n; j++) dp[0][j] = 1;
        
        
        t = " " + t;
        s = " " + s;
        char[] tt = t.toCharArray();
        char[] ss = s.toCharArray();
        
        // 填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                dp[i][j] = tt[i] == ss[j] ? (dp[i][j - 1] + dp[i - 1][j - 1]) : dp[i][j - 1];
            }
        }
        
        return dp[m][n];
    }
}

4.通配符匹配

链接:

https://leetcode.cn/problems/wildcard-matching/

分析:

代码:

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        // 2.初始化
        dp[0][0] = true;
        for(int j = 1; j <= n; j++){
            if(p.charAt(j - 1) == '*') dp[0][j] = true;
            else break;
        }
        s = " " + s;
        p = " " + p;
        char[] ss = s.toCharArray();
        char[] pp = p.toCharArray();
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(pp[j] == '*') dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                else dp[i][j] = (ss[i] == pp[j] || pp[j] == '?') && dp[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }
}

本题的难点就在于当p[j] == '*'时可以匹配任意的子序列 ,那么就有很多种的状态表示,要想办法使用若干个状态去表示.

5. 正则表达式

链接:

https://leetcode.cn/problems/regular-expression-matching/

分析:

初看本题觉得和上一题通配符匹配很相似,于是直接C,V结果发现无法通过(大胆),经过仔细分析发现本题在p[j] == '*'这种情况和上一题不同,上一题的*可以匹配任意的子序列,也就是他的状态是不受到之前状态的影响的,但是本题不一样,题目中明确告知*必须和前一个字符结合才有意义

也就是说,如果p[j] == *,其状态会受到p[j - 1]的影响,所以对于这种情况要单独讨论

一定要注意*可以匹配空串,此时就代表这两个位置的字符无效了

初始化:

本题的初始化和通配符匹配也有所不同,还是那句话,这道题当p[j]==*时的状态是受到前一个字符的影响的

注意本题是不会出现多个*连续出现的,题目规定一个*之前一定有一个有效的字符去进行匹配

代码:

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        // 2.初始化(注意细节)
        dp[0][0] = true;
        for(int j = 2; j <= n; j+= 2){
            if(p.charAt(j - 1) == '*') dp[0][j] = true;
            else break;
        }
        s = " " + s;
        p = " " + p;
        char[] ss = s.toCharArray();
        char[] pp = p.toCharArray();
        // 填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(pp[j] != '*') dp[i][j] = (ss[i] == pp[j] || pp[j] == '.') && dp[i - 1][j - 1];
                else dp[i][j] = dp[i][j - 2] || (pp[j - 1] == '.' || pp[j - 1] == ss[i]) && dp[i - 1][j];
            }
        }
        // 返回值
        return dp[m][n];
    }
}

总结:

  1. 两个数组的dp问题经常是两个字符串之间关系,比如公共子序列的长度,能够匹配多少个目标字符串之类的
  2. 两个字符串的问题也有一些常用的经验和优化
  • 状态表示一般都是s1[0,1]区间内,s2[0,j]区间内巴拉巴拉,比如s1.s2在不同的区间时的最长公共子序列的长度,又或者s2在在不同区间内能包含多少个s1特定区间内的字符串这样的问题,和之前我们惯用的以i位置为结束的状态表示不同
  • 状态转移方程的推到比较难,要结合具体的题目尽心分析,但是大致的方向都相同,即根据最后一个位置的状态去分类讨论
  • 在初始化时往往要引入空串,来应对下标之间的映射关系.对于dp表往往采取增加一行一列的方式进行初始化
  • 返回值一般就是返回dp表中最后一个元素


目录
相关文章
|
1月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
38 0
|
3月前
|
算法 测试技术
【算法】二分算法——寻找旋转排序数组中的最小值
【算法】二分算法——寻找旋转排序数组中的最小值
|
1月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
31 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
1月前
|
存储 算法 定位技术
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
这篇文章主要介绍了稀疏数组和队列的概念、应用实例以及如何使用数组模拟队列和环形队列的实现方法。
21 0
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
|
1月前
|
存储 算法
动态规划算法学习一:DP的重要知识点、矩阵连乘算法
这篇文章是关于动态规划算法中矩阵连乘问题的详解,包括问题描述、最优子结构、重叠子问题、递归方法、备忘录方法和动态规划算法设计的步骤。
101 0
|
1月前
|
算法 C++
【算法】DP背包问题(C/C++)
【算法】DP背包问题(C/C++)
|
1月前
|
人工智能 算法 BI
【算法】 线性DP(C/C++)
【算法】 线性DP(C/C++)
|
3月前
|
存储 算法 Java
深入算法基础二分查找数组
文章深入学习了二分查找算法的基础,通过实战例子详细解释了算法的逻辑流程,强调了确定合法搜索边界的重要性,并提供了Java语言的代码实现。
深入算法基础二分查找数组
|
3月前
|
算法
【Azure Developer】完成算法第4版书中,第一节基础编码中的数组函数 histogrm()
【Azure Developer】完成算法第4版书中,第一节基础编码中的数组函数 histogrm()
|
3月前
|
算法
【算法】模拟算法——外观数组(medium)
【算法】模拟算法——外观数组(medium)