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