网站架构设计师薪资水平,提供网站空间服务器,百度网首页,网站制作的基本流程目录
两个数组dp问题
1.最长公共子序列
2.不同的子序列
3.通配符匹配 本文旨在通过对力扣上三道题进行讲解来让大家对使用动态规划解决两个数组的dp问题有一定思路#xff0c;培养大家对状态定义#xff0c;以及状态方程书写的思维。 顺序#xff1a; 题目链接-》算法思…目录
两个数组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 re0;char[] stext1.toCharArray();char[] s1text2.toCharArray();int ms.length,ns1.length;int[][] dpnew int[m1][n1];for(int i1;im;i){for(int j1;jn;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 MOD1000000007;s s;t t;char[] s1s.toCharArray();char[] s2t.toCharArray();int ns1.length;int ms2.length;int[][] dpnew int[n][m];for(int i0;in;i){dp[i][0]1;}for(int i1;in;i){for(int j1;jm;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[] s1s.toCharArray();char[] s2p.toCharArray();int ns1.length;int ms2.length;boolean[][] dpnew boolean[n][m];dp[0][0]true;for(int i1;im;i){if(s2[i]*){dp[0][i]dp[0][i-1];}}for(int i1;in;i){for(int j1;jm;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];}
}
