精通网站建设pdf下载wordpress博客xiu
目录
两个数组dp问题
1.最长公共子序列
2.不同的子序列
3.通配符匹配
本文旨在通过对力扣上三道题进行讲解来让大家对使用动态规划解决两个数组的dp问题有一定思路，培养大家对状态定义，以及状态方程书写的思维。
顺序：
题目链接-》算法思路-》代码呈现
两个数组dp问题
动态规划类题目解题步骤：
- 依据题目进行状态表示(dp[i]的含义)
- 写出状态转移方程(类似于dp[i]=dp[i-1]+dp[i-2])
- 为防止填表时数组越界，对dp表进行初始化（dp[0]=dp[1]=1）
- 搞清楚填表顺序（从前往后或者从后往前）
- 利用dp表返回问题答案
1.最长公共子序列
题目链接：
https://leetcode.cn/problems/longest-common-subsequence/
算法思路：
1. 状态表⽰：
对于两个数组的动态规划，我们的定义状态表⽰的经验就是：
- 选取第⼀个数组 [0, i] 区间以及第⼆个数组 [0, j] 区间作为研究对象；
- 结合题⽬要求，定义状态表⽰。
在这道题中，我们根据定义状态表⽰为：
dp[i][j] 表⽰： s1 的 [0, i] 区间以及 s2 的 [0, j] 区间内的所有的⼦序列中，最⻓公共⼦序列的⻓度。
2. 状态转移⽅程：
分析状态转移⽅程的经验就是根据「最后⼀个位置」的状况，分情况讨论。
对于 dp[i][j] ，我们可以根据 s1[i] 与 s2[j] 的字符分情况讨论：
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] 结尾。那么我们找最⻓公共⼦序列时，有下⾯三种策略：
- 去 s1 的 [0, i - 1] 以及 s2 的 [0, j] 区间内找：此时最⼤⻓度为 dp[i - 1][j] ；
- 去 s1 的 [0, i] 以及 s2 的 [0, j - 1] 区间内找：此时最⼤⻓度为 dp[i ] [j - 1] ；
- 去 s1 的 [0, i - 1] 以及 s2 的 [0, j - 1] 区间内找：此时最⼤⻓度为dp[i - 1][j - 1] 。
我们要三者的最⼤值即可。但是我们细细观察会发现，第三种包含在第⼀种和第⼆种情况⾥⾯，但是我们求的是最⼤值，并不影响最终结果。因此只需求前两种情况下的最⼤值即可。
综上，状态转移⽅程为：
if(s1[i] == s2[j]) dp[i][j] = dp[i - 1][j - 1] + 1 ;
if(s1[i] != s2[j]) dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) 。
3. 初始化：
- 「空串」是有研究意义的，因此我们将原始 dp 表的规模多加上⼀⾏和⼀列，表⽰空串。
- 引⼊空串后，⼤⼤的⽅便我们的初始化。
- 但也要注意「下标的映射关系」，以及⾥⾯的值要「保证后续填表是正确的」。
当 s1 为空时，没有⻓度，同理 s2 也是。因此第⼀⾏和第⼀列⾥⾯的值初始化为 0 即可保证后续填表是正确的。
4. 填表顺序：
根据「状态转移⽅程」得：从上往下填写每⼀⾏，每⼀⾏从左往右。
5. 返回值：
根据「状态表⽰」得：返回 dp[m][n] 。
代码呈现：
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. 状态表⽰：
对于两个字符串之间的 dp 问题，我们⼀般的思考⽅式如下：
- 选取第⼀个字符串的 [0, i] 区间以及第⼆个字符串的 [0, j] 区间当成研究对象，结合题⽬的要求来定义「状态表⽰」；
- 然后根据两个区间上「最后⼀个位置的字符」，来进⾏「分类讨论」，从⽽确定「状态转移⽅程」。
我们可以根据上⾯的策略，解决⼤部分关于两个字符串之间的 dp 问题。
dp[i][j] 表⽰：在字符串 s 的 [0, j] 区间内的所有⼦序列中，有多少个 t 字符串 [0,i] 区间内的⼦串。
2. 状态转移⽅程：
⽼规矩，根据「最后⼀个位置」的元素，结合题⽬要求，分情况讨论：
1. 当 t[i] == s[j] 的时候，此时的⼦序列有两种选择：
- ⼀种选择是：⼦序列选择 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] ；
两种情况加起来，就是 t[i] == s[j] 时的结果。
2. 当 t[i] != s[j] 的时候，此时的⼦序列只能从 dp[i][j - 1] 中选择所有符合要求的⼦序列。只能继承上个状态⾥⾯求得的⼦序列， dp[i][j] = dp[i][j - 1] ；
综上所述，状态转移⽅程为：
- 所有情况下都可以继承上⼀次的结果： dp[i][j] = dp[i][j - 1] ；
- 当 t[i] == s[j] 时，可以多选择⼀种情况： dp[i][j] += dp[i - 1][j - 1]
3. 初始化：
- 「空串」是有研究意义的，因此我们将原始 dp 表的规模多加上⼀⾏和⼀列，表⽰空串。
- 引⼊空串后，⼤⼤的⽅便我们的初始化。
- 但也要注意「下标的映射关系」，以及⾥⾯的值要「保证后续填表是正确的」。
当 s 为空时， t 的⼦串中有⼀个空串和它⼀样，因此初始化第⼀⾏全部为 1 。
4. 填表顺序：
「从上往下」填每⼀⾏，每⼀⾏「从左往右」。
5. 返回值：
根据「状态表⽰」，返回 dp[m][n] 的值。
本题有⼀个巨恶⼼的地⽅，题⽬上说结果不会超过 int 的最⼤值，但是实际在计算过程会会超。为
了避免报错，我们选择 double 存储结果。
代码呈现：
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. 状态表⽰：
对于两个字符串之间的 dp 问题，我们⼀般的思考⽅式如下：
- 选取第⼀个字符串的 [0, i] 区间以及第⼆个字符串的 [0, j] 区间当成研究对象，结合题⽬的要求来定义「状态表⽰」；
- 然后根据两个区间上「最后⼀个位置的字符」，来进⾏「分类讨论」，从⽽确定「状态转移⽅程」。
我们可以根据上⾯的策略，解决⼤部分关于两个字符串之间的 dp 问题。
因此，我们定义状态表⽰为：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] == '*' 的时候，此时匹配策略有两种选择：
- ⼀种选择是： * 匹配空字符串，此时相当于它匹配了⼀个寂寞，直接继承状态 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) ；
3. 当 p[j] 不是特殊字符，且不与 s[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) ；
优化：当我们发现，计算⼀个状态的时候，需要⼀个循环才能搞定的时候，我们要想到去优化。优
化的⽅向就是⽤⼀个或者两个状态来表⽰这⼀堆的状态。通常就是把它写下来，然后⽤数学的⽅式
做⼀下等价替换：
当 p[j] == '*' 时，状态转移⽅程为：
dp[i][j] = dp[i][j - 1] || dp[i - 1][j - 1] || dp[i - 2][j - 1]
......
我们发现 i 是有规律的减⼩的，因此我们去看看 dp[i - 1][j] ：
dp[i - 1][j] = dp[i - 1][j - 1] || dp[i - 2][j - 1] || dp[i - 3][j - 1] ...... 我们惊奇的发现， dp[i][j] 的状态转移⽅程⾥⾯除了第⼀项以外，其余的都可以⽤ dp[i - 1][j] 替代。因此，我们优化我们的状态转移⽅程为： dp[i][j] = dp[i - 1][j] || dp[i][j - 1] 。
3. 初始化：
由于 dp 数组的值设置为是否匹配，为了不与答案值混淆，我们需要将整个数组初始化为false 。
由于需要⽤到前⼀⾏和前⼀列的状态，我们初始化第⼀⾏、第⼀列即可。
- dp[0][0] 表⽰两个空串能否匹配，答案是显然的， 初始化为 true 。
- 第⼀⾏表⽰ s 是⼀个空串， p 串和空串只有⼀种匹配可能，即 p 串表⽰为 "***" ，此时 也相当于空串匹配上空串。所以，我们可以遍历 p 串，把所有前导为 "*" 的 p ⼦串和空串 的 dp 值设为 true 。
- 第⼀列表⽰ p 是⼀个空串，不可能匹配上 s 串，跟随数组初始化即可。
4. 填表顺序：
从上往下填每⼀⾏，每⼀⾏从左往右。
5. 返回值：
根据状态表⽰，返回 dp[m][n] 的值。
代码呈现：
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];}
}