🎋前言
动态规划相关题目都可以参考以下五个步骤进行解答：
- 状态表示
- 状态转移⽅程
- 初始化
- 填表顺序
- 返回值
后面题的解答思路也将按照这五个步骤进行讲解。
🌴最长公共子序列
🚩题目描述
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
- 例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
- 示例 1：
输入：text1 = “abcde”, text2 = “ace”
输出：3
解释：最长公共子序列是 “ace” ，它的长度为 3 。 - 示例 2：
输入：text1 = “abc”, text2 = “abc”
输出：3
解释：最长公共子序列是 “abc” ，它的长度为 3 。 - 示例 3：
输入：text1 = “abc”, text2 = “def”
输出：0
解释：两个字符串没有公共子序列，返回 0 。
class Solution { public int longestCommonSubsequence(String text1, String text2) { } }
🚩算法思路
- 状态表⽰：
对于两个数组的动态规划，我们的定义状态表⽰的经验就是：
- 选取第⼀个数组 [0, i] 区间以及第⼆个数组 [0, j] 区间作为研究对象；
- 结合题⽬要求，定义状态表⽰。
在这道题中，我们根据定义状态表⽰为：
dp[i][j] 表⽰： text1 的 [0, i] 区间以及 text2 的 [0, j] 区间内的所有的⼦序列中，最⻓公共⼦序列的⻓度。
- 状态转移⽅程：
分析状态转移⽅程的经验就是根据「最后⼀个位置」的状况，分情况讨论。
对于 dp[i][j] ，我们可以根据 text1[i] 与 text2[j] 的字符分情况讨论：
- 两个字符相同， text1[i] = text2[j] ：那么最⻓公共⼦序列就在 text1 的 [0, i - 1] 以及 text2 的 [0, j - 1] 区间上找到⼀个最⻓的，然后再加上 text1[i] 即可。因此dp[i][j] = dp[i - 1][j - 1] + 1 ；
- 两个字符不相同， text1[i] != text2[j] ：那么最⻓公共⼦序列⼀定不会同时以 text1[i] 和 text2[j] 结尾。那么我们找最⻓公共⼦序列时，有下⾯三种策略：
- 去 text1 的 [0, i - 1] 以及text2 的 [0, j] 区间内找：此时最⼤⻓度为 dp[i- 1][j] ；
- 去 text1 的 [0, i] 以及 text2 的 [0, j - 1] 区间内找：此时最⼤⻓度为 dp[i ][j - 1] ；
- 去text1 的 [0, i - 1] 以及text2 的 [0, j - 1] 区间内找：此时最⼤⻓度为dp[i - 1][j - 1] 。
我们要三者的最⼤值即可。但是我们细细观察会发现，第三种包含在第⼀种和第⼆种情况⾥⾯，但是我们求的是最⼤值，并不影响最终结果。因此只需求前两种情况下的最⼤值即可。
综上，状态转移⽅程为：
if(text1[i] == text2[j]) dp[i][j] = dp[i - 1][j - 1] + 1 ;
if(text1[i] != text2[j]) dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) 。
- 初始化：
要注意「下标的映射关系」，以及⾥⾯的值要「保证后续填表是正确的」。
- 填表顺序：
根据「状态转移⽅程」得：从上往下填写每⼀⾏，每⼀⾏从左往右。
- 返回值：
根据「状态表⽰」得：返回 dp[m][n] 。
🚩代码实现
class Solution { public int longestCommonSubsequence(String text1, String text2) { int m = text1.length(); int n = text2.length(); int[][] dp = new int[m + 1][n + 1]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if(text1.charAt(i - 1) == text2.charAt(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]; } }
🎄不相交的线
🚩题目描述
在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。
现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足：
nums1[i] == nums2[j]
且绘制的直线不与任何其他连线（非水平线）相交。
请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。
以这种方法绘制线条，并返回可以绘制的最大连线数。
- 示例 1：
输入：nums1 = [1,4,2], nums2 = [1,2,4]
输出：2
解释：可以画出两条不交叉的线，如上图所示。
但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。 - 示例 2：
输入：nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
输出：3 - 示例 3：
输入：nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
输出：2
class Solution { public int maxUncrossedLines(int[] nums1, int[] nums2) { } }
🚩算法思路
如果要保证两条直线不相交，那么我们「下⼀个连线」必须在「上⼀个连线」对应的两个元素的「后⾯」寻找相同的元素。这不就转化成「最⻓公共⼦序列」的模型了嘛。那就是在这两个数组中寻找「最⻓的公共⼦序列」。
只不过是在整数数组中做⼀次「最⻓的公共⼦序列」，代码⼏乎⼀模⼀样，这⾥就不再赘述算法原理啦~
🚩代码实现
class Solution { public int maxUncrossedLines(int[] nums1, int[] nums2) { // 1. 创建 dp 表 // 2. 初始化 // 3. 填表 // 4. 返回值 int m = nums1.length; int n = nums2.length; int[][] dp = new int[m + 1][n + 1]; for(int i = 1; i <= m; i++) { for(int j = 1; j <= n; j++) { if(nums1[i - 1] == nums2[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]; } }
🎍不同的子序列
🚩题目描述
给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。
- 示例 1：
输入：s = “rabbbit”, t = “rabbit”
输出：3 - 示例 2：
输入：s = “babgbag”, t = “bag”
输出：5
class Solution { public int numDistinct(String s, String t) { } }
🚩算法思路
- 状态表⽰：
对于两个字符串之间的 dp 问题，我们⼀般的思考⽅式如下：
- 选取第⼀个字符串的 [0, i] 区间以及第⼆个字符串的 [0, j] 区间当成研究对象，结合题⽬的要求来定义「状态表⽰」；
- 然后根据两个区间上「最后⼀个位置的字符」，来进⾏「分类讨论」，从⽽确定「状态转移⽅程」。
我们可以根据上⾯的策略，解决⼤部分关于两个字符串之间的 dp 问题。
dp[i][j] 表⽰：在字符串 s 的 [0, j] 区间内的所有⼦序列中，有多少个 t 字符串 [0,i] 区间内的⼦串。
- 状态转移⽅程：
⽼规矩，根据「最后⼀个位置」的元素，结合题⽬要求，分情况讨论：
- 当 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] 时的结果。
- 当 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]
- 初始化：
- 「空串」是有研究意义的，因此我们将原始 dp 表的规模多加上⼀⾏和⼀列，表⽰空串。
- 引⼊空串后，⼤⼤的⽅便我们的初始化。
- 但也要注意「下标的映射关系」，以及⾥⾯的值要「保证后续填表是正确的」。
当 s 为空时， t 的⼦串中有⼀个空串和它⼀样，因此初始化第⼀⾏全部为 1 。
- 填表顺序：
「从上往下」填每⼀⾏，每⼀⾏「从左往右」。
- 返回值：
根据「状态表⽰」，返回 dp[m][n] 的值，本题不用取模也可通过
🚩代码实现
class Solution { public int numDistinct(String s, String t) { // 1. 创建 dp 表 // 2. 初始化 // 3. 填表 // 4. 返回值 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; } for(int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { dp[i][j] = dp[i][j - 1]; if (t.charAt(i - 1) == s.charAt(j - 1)) { dp[i][j] += dp[i - 1][j - 1]; } } } return dp[m][n]; } }
🍀通配符匹配
🚩题目描述
给你一个输入字符串 (s) 和一个字符模式 § ，请你实现一个支持 ‘?’ 和 ‘*’ 匹配规则的通配符匹配：
- ‘?’ 可以匹配任何单个字符。
- ‘*’ 可以匹配任意字符序列（包括空字符序列）。
判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。
- 示例 1：
输入：s = “aa”, p = “a”
输出：false
解释：“a” 无法匹配 “aa” 整个字符串。 - 示例 2：
输入：s = “aa”, p = ""
输出：true
解释：'’ 可以匹配任意字符串。 - 示例 3：
输入：s = “cb”, p = “?a”
输出：false
解释：‘?’ 可以匹配 ‘c’, 但第二个 ‘a’ 无法匹配 ‘b’。
class Solution { public boolean isMatch(String ss, String pp) { } }
🚩算法思路：
- 状态表⽰：
对于两个字符串之间的 dp 问题，我们⼀般的思考⽅式如下：
- 选取第⼀个字符串的 [0, i] 区间以及第⼆个字符串的 [0, j] 区间当成研究对象，结合题⽬的要求来定义「状态表⽰」；
- 然后根据两个区间上「最后⼀个位置的字符」，来进⾏「分类讨论」，从⽽确定「状态转移
⽅程」。
我们可以根据上⾯的策略，解决⼤部分关于两个字符串之间的 dp 问题。
因此，我们定义状态表⽰为：
dp[i][j] 表⽰： p 字符串 [0, j] 区间内的⼦串能否匹配字符串 s 的 [0, i] 区间内的
⼦串。
- 状态转移⽅程：
⽼规矩，根据最后⼀个位置的元素，结合题⽬要求，分情况讨论：
- 当 s[i] == p[j] 或 p[j] == ‘?’ 的时候，此时两个字符串匹配上了当前的⼀个字符，只能从 dp[i - 1][j - 1] 中看当前字符前⾯的两个⼦串是否匹配。只能继承上个状态中的匹配结果， dp[i][j] = dp[i][j - 1] ；
- 当 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) ；
- 当 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] 。
- 初始化：
由于 dp 数组的值设置为是否匹配，为了不与答案值混淆，我们需要将整个数组初始化为false 。
由于需要⽤到前⼀⾏和前⼀列的状态，我们初始化第⼀⾏、第⼀列即可。
- dp[0][0] 表⽰两个空串能否匹配，答案是显然的，初始化为 true 。
- 第⼀⾏表⽰ s 是⼀个空串， p 串和空串只有⼀种匹配可能，即 p 串表⽰为 “**" ，此时也相当于空串匹配上空串。所以，我们可以遍历 p 串，把所有前导为 "” 的 p ⼦串和空串的 dp 值设为 true 。
- 第⼀列表⽰ p 是⼀个空串，不可能匹配上 s 串，跟随数组初始化即可。
- 填表顺序：
从上往下填每⼀⾏，每⼀⾏从左往右。
- 返回值：
根据状态表⽰，返回 dp[m][n] 的值。
🚩代码实现
class Solution { public boolean isMatch(String ss, String pp) { // 1. 创建 dp 表 // 2. 初始化 // 3. 填表 // 4. 返回结果 int m = ss.length(); int n = pp.length(); ss = " " + ss; pp = " " + pp; char[] s = ss.toCharArray(); char[] p = pp.toCharArray(); boolean[][] dp = new boolean[m + 1][n + 1]; dp[0][0] = true; for(int j = 1; j <= n; j++) { if(p[j] == '*') { dp[0][j] = true; } else { break; } } for(int i = 1; i <= m; i++) { for(int j = 1; j <= n; j++) { if(p[j] == '*') { dp[i][j] = dp[i - 1][j] || dp[i][j - 1]; } else { dp[i][j] = (p[j] == '?' || p[j] == s[i]) && dp[i - 1][j - 1]; } } } return dp[m][n]; } }
⭕总结
关于《【算法优选】 动态规划之两个数组dp——壹》就讲解到这儿，感谢大家的支持，欢迎各位留言交流以及批评指正，如果文章对您有帮助或者觉得作者写的还不错可以点一下关注，点赞，收藏支持一下
