【算法篇】逐步理解动态规划模型7（两个数组dp问题）

目录

两个数组dp问题

1.最长公共子序列

2.不同的子序列

3.通配符匹配

---

        本文旨在通过对力扣上三道题进行讲解来让大家对使用动态规划解决两个数组的dp问题有一定思路，培养大家对状态定义，以及状态方程书写的思维。

顺序：

题目链接-》算法思路-》代码呈现

两个数组dp问题

动态规划类题目解题步骤：

1. 依据题目进行状态表示(dp[i]的含义)
2. 写出状态转移方程(类似于dp[i]=dp[i-1]+dp[i-2])
3. 为防止填表时数组越界，对dp表进行初始化（dp[0]=dp[1]=1）
4. 搞清楚填表顺序（从前往后或者从后往前）
5. 利用dp表返回问题答案

1.最长公共子序列

题目链接：

https://leetcode.cn/problems/longest-common-subsequence/

算法思路：

1. 选取第⼀个数组 [0, i] 区间以及第⼆个数组 [0, j] 区间作为研究对象；
2. 结合题⽬要求，定义状态表⽰。

代码呈现：

class Solution {public int longestCommonSubsequence(String text1, String text2) {int re=0;char[] s=text1.toCharArray();char[] s1=text2.toCharArray();int m=s.length,n=s1.length;int[][] dp=new int[m+1][n+1];for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(s[i-1]==s1[j-1]){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[m][n];}
}

2.不同的子序列

题目链接：

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

算法思路：

1. 选取第⼀个字符串的 [0, i] 区间以及第⼆个字符串的 [0, j] 区间当成研究对象，结合题⽬的要求来定义「状态表⽰」；
2. 然后根据两个区间上「最后⼀个位置的字符」，来进⾏「分类讨论」，从⽽确定「状态转移⽅程」。

• ⼀种选择是：⼦序列选择 s[j] 作为结尾，此时相当于在状态 dp[i - 1][j - 1]中的所有符合要求的⼦序列的后⾯，再加上⼀个字符 s[j] （请⼤家结合状态表⽰，好好理解这句话），此时 dp[i][j] = dp[i - 1][j - 1] ；
• 另⼀种选择是：我就是任性，我就不选择 s[j] 作为结尾。此时相当于选择了状态dp[i][j - 1] 中所有符合要求的⼦序列。我们也可以理解为继承了上个状态⾥⾯的求得的⼦序列。此时 dp[i][j] = dp[i][j - 1] ；

代码呈现：

class Solution {public int numDistinct(String s, String t) {int MOD=1000000007;s=" "+s;t=" "+t;char[] s1=s.toCharArray();char[] s2=t.toCharArray();int n=s1.length;int m=s2.length;int[][] dp=new int[n][m];for(int i=0;i<n;i++){dp[i][0]=1;}for(int i=1;i<n;i++){for(int j=1;j<m;j++){dp[i][j]=dp[i-1][j];if(s1[i]==s2[j]){dp[i][j]+=dp[i-1][j-1];}}}return dp[n-1][m-1];}
}

3.通配符匹配

题目链接：

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

算法思路：

1. 选取第⼀个字符串的 [0, i] 区间以及第⼆个字符串的 [0, j] 区间当成研究对象，结合题⽬的要求来定义「状态表⽰」；
2. 然后根据两个区间上「最后⼀个位置的字符」，来进⾏「分类讨论」，从⽽确定「状态转移⽅程」。

• ⼀种选择是： * 匹配空字符串，此时相当于它匹配了⼀个寂寞，直接继承状态 dp[i][j - 1] ，此时 dp[i][j] = dp[i][j - 1] ；
• 另⼀种选择是： * 向前匹配 1 ~ n 个字符，直⾄匹配上整个 s1 串。此时相当于从 dp[k][j - 1] (0 <= k <= i) 中所有匹配情况中，选择性继承可以成功的情况。此时 dp[i][j] = dp[k][j - 1] (0 <= k <= i) ；

• 当 s[i] == p[j] 或 p[j] == '?' 时： dp[i][j] = dp[i][j - 1] ；
• 当 p[j] == '*' 时，有多种情况需要讨论： dp[i][j] = dp[k][j - 1] (0 <=k <= i) ；

代码呈现：

class Solution {public boolean isMatch(String s, String p) {s=" "+s;p=" "+p; char[] s1=s.toCharArray();char[] s2=p.toCharArray();int n=s1.length;int m=s2.length;boolean[][] dp=new boolean[n][m];dp[0][0]=true;for(int i=1;i<m;i++){if(s2[i]=='*'){dp[0][i]=dp[0][i-1];}}for(int i=1;i<n;i++){for(int j=1;j<m;j++){if(s2[j]=='?'||s1[i]==s2[j]){dp[i][j]=dp[i-1][j-1];}if(s2[j]=='*'){dp[i][j]=dp[i][j-1]||dp[i-1][j];}}}return dp[n-1][m-1];}
}