【算法】【动规】双数组系列问题
跳转汇总链接
4.1 最长公共子序列
给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。
一个字符串的 子序列
是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。
例如,“ace” 是 “abcde” 的子序列,但 “aec” 不是 “abcde” 的子序列。 两个字符串的 公共子序列
是这两个字符串所共同拥有的子序列。
- 状态表示
- dp[i][j] 表示,text1 的 [0, i] 区间和 text2 的 [0, j] 区间中,的最长公共子序列的长度
- 状态转移方程
-
分析 i 和 j 位置,如果字符相等,那么其区间中的最长公共子序列一定可以以这个字符为结尾;如果不等,再分情况讨论
dp[i][j] 的值有如下情况需要考虑: text1[i] == text2[j], dp[i-1][j-1] + 1; text1[i] != text2[j], 对如下值取 max: dp[i-1][j] dp[i][j-1] dp[i-1][j-1] // 实际上这个情况已经被头两种包含了,可以不用写
-
- 初始化
- 需要考虑 i-1、j-1 的越界情况,我们可以对空串进行设置,可以有效的防止越界
- 这里在二维数组的前面多加一行和一列,分别表示两个数组为空串时候的 dp 值
- 注意访问原数组时的对齐
- 将空串也作为公共子序列,把多加的一行和一列都初始化为 0
- 填表顺序
- 从上往下填写每一行,每行从左往右填写
- 返回值
- dp[text1.size()][text2.size()],表的最右下角的值。
🐎代码如下:
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int n1 = text1.size() + 1;
int n2 = text2.size() + 1;
text1 = "-" + text1;
text2 = "-" + text2;
vector<vector<int>> dp(n1, vector<int>(n2));
for(int i = 1; i < n1; i++)
for(int j = 1; j < n2; j++)
if (text1[i] == text2[j])
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
return dp[n1-1][n2-1];
}
};
4.2 不相交的线
在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。
现在,可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线,这些直
线需要同时满足满足:
nums1[i] == nums2[j] 且绘制的直线不与任何其他连线(非水平线)相交。
请注意,连线即使在端点也不能相交:每个数字只能属于一条连线。以这种方法绘制线条,并返回可以绘制的最大连线数。
状态表示
- dp[i][j] 表示,text1 的 [0, i] 区间和 text2 的 [0, j] 区间中,的最大连线数
略…(这一题和 4.1 根本是一样的,不交叉的连线不就是公共子序列嘛)
🐎代码如下:
class Solution {
public:
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
int n1 = nums1.size() + 1;
int n2 = nums2.size() + 1;
vector<vector<int>> dp(n1, vector<int>(n2));
for(int i = 1; i < n1; i++)
for(int j = 1; j < n2; j++)
if (nums1[i-1] == nums2[j-1]) // 访问原数组的时候注意一下位置
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
return dp[n1-1][n2-1];
}
};
4.3 不同的子序列(hard)
给你两个字符串 s 和 t ,统计并返回在 s 的 子序列 中 t 出现的个数,结果需要对 109 + 7 取模。
这一题 hard 在状态表示…
- 状态表示
- dp[i][j] 表示,s 的 [0, i] 区间中有多少个子序列,满足和 t 的 [0, j] 区间的子串相同
- 状态转移方程
-
分析区间内的 s 和 t 串,这里如果 s[i] 算作子序列的结尾 dp 是一种情况,如果 s[i] 不算作子序列的结尾 dp 又会是另一种情况,而最终这里的 dp 值应该是这两种情况相加。
dp[i][j] 的值有如下情况需要考虑: s[i] 算作结尾,而且 s[i] == t[j], dp[i-1][j-1] s[i] 不算作结尾, dp[i-1][j] 条件满足的情况下:dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
-
- 初始化
- 需要考虑 i-1、j-1 的越界情况,我们可以对空串进行设置,可以有效的防止越界
- 这里在二维数组的前面多加一行和一列,分别表示两个数组为空串时候的 dp 值
- 注意访问原数组时的对齐
- 将空串也作为公共子序列,dp[i][0] 位置都置 1,意思是 t 为空串的时候 s 最少也包含这一个空串
- 在 for 循环的时候初始化即可
- 填表顺序
- 从上往下填写每一行,每行从左往右填写
- 返回值
- dp[s.size()][t.size()],表的最右下角的值。
🐎代码如下:
class Solution {
public:
int numDistinct(string s, string t) {
int n1 = s.size() + 1;
int n2 = t.size() + 1;
vector<vector<double>> dp(n1, vector<double>(n2));
dp[0][0] = 1;
for(int i = 1; i < n1; i++)
{
dp[i][0] = 1;
for(int j = 1; j < n2; j++)
dp[i][j] = (s[i-1] == t[j-1]) ?
dp[i-1][j] + dp[i-1][j-1] :
dp[i-1][j];
}
return dp[n1-1][n2-1];
}
};
🥰如果本文对你有些帮助,欢迎👉 点赞 收藏 关注,你的支持是对作者大大莫大的鼓励!!(????) 若有差错恳请留言指正~~
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!