【动态规划】两个数组的 dp 问题一
两个数组的 dp 问题
- 1.最长公共子序列
- 2.不相交的线
- 3.不同的子序列
- 4.通配符匹配
点赞👍👍收藏🌟🌟关注💖💖
你的支持是对我最大的鼓励，我们一起努力吧!😃😃
1.最长公共子序列
题目链接：1143. 最长公共子序列
题目描述：
算法原理：
1.状态表示
这道题是遇到新的类型的题，两个字符串的dp问题。并且求的是最长公共子序列，我们很多题的经验就是从这道题来到。我们先总结一下这个经验。
经验 + 题目要求
- 选取第一个字符串 [0, i] 区间以及第二个字符串 [0, j] 区间作为研究对象
- 根据题目要求，确定状态表示
先以这两段区间来研究，这道题研究的是最长公共子序列。也就是说先看看上面s1这个区间所有子序列，以及下面s2这个区间所有子序列，其中的最长子序列。
dp[i][j] 表示：s1 的 [0, i] 区间以及 s2 的[0, j] 区间内所有子序列中，最长公共子序列的长度。
如果以某个位置为结尾所有子序列，还有在去找子序列，时间复杂O(N^4)，而我们这里的子序列是所有的子序列，比如是说 [0,i] 区间所有的子序列。这个子序列既包含以i为结尾，也包含不以i为结尾的。
2.状态转移方程
根据最后一个位置的情况，分情况讨论
如果最后一个位置字符相等 s[i] == s[j]
是不是可以先在s1 [ 0 , i-1] 和 s2 [0 , j - 1]区间内所有子序列找最长公共子序列长度 然后 加上 1就行了
如果最后一个位置字符相等 s[i] != s[j]
那么最长公共子序列一定不是以 i j 位置为结尾，也就是说最长公共子序列一定不是同时选择 i 和 j 位置。那可以这样选
- s1[0, i - 1]，s2[0, j] ，不选 i
- s1[0, i]，s2[0, j -1] ，不选 j
- s1[0, i - 1]，s2[0, j - 1]， i j都不选
我们一般找状态转移方程要把所有情况不重不漏都找完，情况1 和 情况2 都包含情况3。但是注意我们的状态表示是最长公共子序列的长度，我们要找的是多种情况的max。所有这里的重复不会影响。但是如果要找的是公共子序列的个数，那就有问题了。遇到了再说。还有情况1和情况2包括情况3，所以填表的时候情况3就不用考虑了。
3.初始化
关于字符串的 dp 问题： 空串是有研究意义的
比如 s1 选一个空串，s2 选一个空串，其实也是一个公共子序列，不过公共子序列长度为0。
引入空串的概念之后，会方便我们的初始化
s1 [0，i] 区间，i最小0，最差就是 [0，0]是一定有一个字符的，如何表示空串呢？可以在原始 dp 表上多来一行一列，第一行表示第一个字符串为空，第二行表示第二个字符串为空。
并且填表也不会越界了。而且第一行表示第一个字符串为空，所以最长公共子序为0，第一列表示第二个字符串为空，所以最长公共子序也是0。
引入辅助节点要注意两个注意事项：
- 里面的值要保证我们后序填表是正确的
- 下标的映射关系
因为多开一行一列相当于dp表向右下移动一位，如果要回原表肯定是要 i-1，j-1。但是在字符串这里，我们可以在每个字符串前面加一个 ‘ ’，然后字符串有效字符就从1开始计数了。这个时候填表 1，1位置的时候就是对应字符串1，1位置。
4.填表顺序
填 i j 会遇到左上，上，左，因此从上往下填写每一行，每一行从左往右
5.返回值
dp[i][j] 表示：s1 的 [0, i] 区间以及 s2 的[0, j] 区间内所有子序列中，最长公共子序列的长度，而我们要的是s1，s2整个字符串的最长子序列的长度。因此 返回 dp[m][n]
class Solution {
public:int longestCommonSubsequence(string s1, string s2) {// 1.创建 dp 表// 2.初始化// 3.填表// 4.返回值int m = s1.size(), n = s2.size();s1 = ' ' + s1, s2 = ' ' + s2;// 处理下标映射关系vector<vector<int>> dp(m + 1, vector<int>(n + 1));// 建表 + 初始化for(int i = 1; i <= m; ++i) // 从上往下每⼀⾏for(int j = 1; j <= n; ++j)// 每⼀⾏从左往右//if(s1[i - 1] == s2[j - 1])if(s1[i] == s2[j])dp[i][j] = dp[i - 1][j - 1] + 1;elsedp[i][j] = max(dp[i - 1][j],dp[i][j - 1]); // 返回结果return dp[m][n];}
};
2.不相交的线
题目链接： 1035. 不相交的线
题目分析：
给两条独立的水平线按给定的顺序写下 nums1 和 nums2 中的整数。
可以以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足：
nums1[i] == nums2[j]
且绘制的直线不与任何其他连线（非水平线）相交。
请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。
以这种方法绘制线条，并返回可以绘制的最大连线数。
先分析一下这道题，下面的最终结果，发现上面数组选252，下面数组也选252。这两个是一样的。是不是相当于在第一个数组中选一个子序列，然后在第二个数组里面也选一个子序列。然后选的这两个子序列要求必须得一样，且最长。那么正好是这两个数组里面得最长公共子序列。
由于这道题和上面几乎一模一样，一些细节就不在细说了
算法原理：
1.状态表示
经验 + 题目要求
- 选取第一个字符串 [0, i] 区间以及第二个字符串 [0, j] 区间作为研究对象
- 根据题目要求，确定状态表示
dp[i][j] 表示 ：在n1里面的 [0,i] 区间以及 n2里面的 [0,j] 区间里面的所有子序列中，最长公共子序列的长度
2.状态转移方程
3.初始化
多开一行一列，填表就不会越界了。
- 里面的值要保证后序填表是正确的
- 下标的映射关系
第一行表示第一个数组里面是没有元素的。第一列表示第二个数组里面没有元素。因此给0。
整体往右下，填表要注意下标映射关系。
4,填表顺序
5.返回值
返回dp[m][n]
class Solution {
public:int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {// 1.创建 dp 表// 2.初始化// 3.填表// 4.返回值int m = nums1.size(), n = nums2.size();vector<vector<int>> dp(m + 1, vector<int>(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;elsedp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);return dp[m][n];}
};
3.不同的子序列
题目链接：115. 不同的子序列
题目分析：
返回s 的 子序列 中 t 出现的个数
算法原理：
1.状态表示
经验 + 题目要求
- 选取第一个字符串 [0, i] 区间以及第二个字符串 [0, j] 区间作为研究对象
- 根据题目要求，确定状态表示
先不考虑整个字符串，先考虑 t [0, i] 区间，以及 s [0, j] 区间，先研究这两个小区间。我们题目要求在s的子序列里有多少个t，如果选这两个子区间的话相当于在 [0, j]这个区间里面的子序列里找一下有多少个 [0,i]子串。
所以我们的状态表示：
dp[i][j] 表示：s字符串 [0, j] 区间内所有子序列中，有多少个 t 字符串 [0, i] 区间内的子串
2.状态转移方程
我们是在s的 [0 ,j]子序列中找找有多少t [0,i] 子串。其实可以把 s 中 [0 ,j] 所有子序列划分成两类。
根据 s 的子序列的最后一个位置包不包含 s[j] 划分两类：
包含s[j]。子序列最后一个位置是j，我们要找子序列有多少t，那子序列要想有t，说明 t 最后一个位置和 j 是相等的。t[i] == s[j]，要求dp[i][j]，既然最后一个位置t[i] == s[j]，可以先把它们去掉，然后在 t [0, i -1] 和 s [0 , j-1]研究问题，也就是说在 s [0 , j-1]里所有子序列中有多少个t [0, i -1] 子串。如果找到有多少个然后后面填上t[i] 和 s[j] 就行了。那有多少个呢？正好是 dp[i - 1][ j - 1]，后面不加1。
不包含s[j]，那就在 s [0, j -1] 所有子序列中找 t [0, i] 子串。
最后dp[i][j] 是这两种情况加起来
3.初始化
- 引入空串
- 里面的值要保证后序填表是正确的
- 下标的映射关系
引入空串就是在原始的dp中上面多加一行，左边多加一列。
第一行表示第一个字符串为空
第一列表示第二个字符串为空
这样填表就不会发生越界了
接下来看里面的值应该填多少
在字符串里，可以根据空串的性质初始化这些位置。
第一行表示 t 字符串为空串，t 如果是空串，s 不管是多长子序列里面都有一个空串。因此第一行应该全都是1
第一列表示 s 字符串为空串，只有当 t 是一个空串，才有一个子序列。 当 t 不是空串，怎么在 s 中也找不到一个子序列是 t。所有除了第一个位置外其他都是0。
下标映射关系。有两种方法
- 每个字符串前面加一个任意字符 s = ‘ ’ + s
- 整体往右下移动一步，回原本要-1
4.填表顺序
从上往下每一行，每一行从左往右
5.返回值
dp[i][j] 表示：s字符串 [0, j] 区间内所有子序列中，有多少个 t 字符串 [0, i] 区间内的子串。题目要求返回在 s 的 子序列 中 t 出现的个数。
class Solution {
public:int numDistinct(string s, string t) {// 1.创建 dp 表// 2.初始化// 3.填表// 4.返回int m = t.size(), n = s.size();vector<vector<double>> dp(m + 1, vector<double>(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[i - 1] == s[j - 1])dp[i][j] += dp[i - 1][j - 1];}}return dp[m][n];}
};
4.通配符匹配
题目链接：44. 通配符匹配
题目描述：
算法原理：
1.状态表示
经验 + 题目要求
dp[i][j] 表示：p[0, j] 区间内的子串能否匹配 s[0, i] 区间内的子串
2.状态转移方程
根据最后一个位置的状况，分情况讨论
p[j]是普通字符，如果 i 位置 和 j 位置字符相等，并且 s [0, i - 1]能被 p[0, j -1] 匹配上，那 [0, i] 就能被 [0, j] 匹配上
p[j] == ‘?’ ，'?'可以匹配任何单个字符，因此只用去看s [0, i - 1]能否被 p[0, j -1] 匹配上
p[j] == ’ * '，（ ’ * ’ 可以匹配任意字符序列（包括空字符序列）。）
如果p[j]匹配空串，我们就看dp[i][j-1]
如果p[j]匹配1个字符，我们就看dp[i-1][j-1]
如果p[j]匹配2个字符，我们就看dp[i-2][j-1]
…
dp[i][j] 时间复杂度就是O(N^2)，在加上p[j] == ’ * '，时间复杂度就是O(N^3)了。想个办法看看p[j] == ’ * '，能否由若干个有限的状态表示。
优化：
第一种方法：数学
p[j] == ‘*’，有这么多种情况，只要有一种情况为真就可以了，所以我们可以得到下面的等式。发现 j -1是不变的，让等式所有 i 都减1。然后就可以进行替换了。
第二种方法：根据状态表示以及实际情况，优化状态转移方程
p[j] == ‘*’，找到dp[i][j]。
当j位置是 ‘*’，第一种情况还是去匹配空串。
第二种情况，去匹配一个字符 ，但是匹配完不把 j 位置丢掉，继续去看 s[0, i -1] 能否被 p[0, j]匹配
可能会有疑问，为什么’ * ‘就匹配一个，明明可以匹配多个，并且匹配完为什么不把’ * '丢掉。
我们这里是对 p[j] == ’ * ’ 好多情况的优化，我们让p[j] == ’ * ‘只匹配一个，但不舍去得到的 dp[i-1][j]，也就是说在dp[i-1][j] 这一个状态里面，j位置 依旧是’ * '，它依旧有两种情况，要么去匹配空串，要么i-1匹配上，然后去dp[i-2][j]考虑匹配2个字符的情况。同理在dp[i-3][j]考虑匹配3个字符的情况。也就是说这个 j 会向下传递直到把s[0,i]所有字符匹配。
也就是说当匹配一个，不丢弃的话，进入dp[i-1][j]，’ * ’ 继续会把 i -1匹配掉。同理进入dp[i-2][j]，’ * ’ 继续会把 i -2匹配掉。。。所有仅需匹配一个不丢弃就可以把所有情况都考虑掉。
3.初始化
- 引入空串
- 里面的值要保证后序的填表是正确的
- 下标的映射关系
dp表上面多加一行表示s是空串，左边多加一列表示p是空串。接下来看看里面值应该填什么。
当 s 是空串，p也是空串，肯定能匹配上，所以第一行第一个格子是true
当s 是空串，但是 p 不是空串的话，注意 ’ * ‘ 可以匹配空串。现在就要对p的字符串就行讨论，然后初始化第一行后面的位置，如果s是空字符串，p字符串 前面出现’ * ‘ 可以匹配空串，但是 ’ * ‘ 之后出现普通字符了，后面不管有多少个’ * '都不能匹配了。
现在考虑第一列，如果p是空串，s也是空串，肯定能匹配，所以第一列第一个空格还是true。
后续如果 p 是空串，s不是空串，肯定匹配不上，所以第一列后续都是false
下标映射有两种方法：
- dp表多加一行一列整体向右下移动一位，如果要回原表需要 i -1，j -1 才行
- s = ’ ‘ + s，字符串前面加一个辅助字符，这样字符串字符就和dp表一一对应了。
4.填表顺序
从上往下填写每一行，每一行从左往右
5.返回值
dp[i][j] 表示：p[0, j] 区间内的子串能否匹配 s[0, i] 区间内的子串。题目要求是整个字符串，因此返回dp[m][n]，m是s的长度，n是p的长度
class Solution {
public:bool isMatch(string s, string p) {// 1.创建 dp 表// 2.初始化// 3.填表// 4.返回值int m = s.size(), n = p.size();vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));//初始化dp[0][0] = true;for(int j = 1; j <= n; ++j)if(p[j - 1] == '*') dp[0][j] = true;else break;for(int i = 1; i <= m; ++i)for(int j = 1; j <= n; ++j)if((s[i - 1] == p[j - 1] || p[j - 1] == '?') && dp[i - 1][j - 1])dp[i][j] = true;else if(p[j - 1] == '*')dp[i][j] = dp[i][j - 1] || dp[i - 1][j];return dp[m][n];}
};