115. 不同的子序列
题目链接:https://leetcode.cn/problems/distinct-subsequences/
文章讲解:https://programmercarl.com/0115.不同的子序列.html
题目难度:困难
视频讲解:https://www.bilibili.com/video/BV1fG4y1m75Q/
题目状态:看题解
思路:
- 动态规划数组初始化
- 创建一个二维动态规划数组
dp
,大小为 ((s.size() + 1), (t.size() + 1))。dp[i][j]
表示s
的前i
个字符中包含t
的前j
个字符的不同子序列的数量。
- 创建一个二维动态规划数组
- 边界条件设置
dp[i][0] = 1
:表示任何字符串s
的前i
个字符都可以形成空字符串t
的一种方式(即选择不选)。dp[0][j] = 0
(对于 (j > 0)):表示空字符串s
无法形成非空字符串t
。
- 动规数组更新
- 外层循环遍历
s
的每个字符(从1
到s.size()
)。 - 内层循环遍历
t
的每个字符(从1
到t.size()
)。 - 如果
s[i-1]
和t[j-1]
相等:dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
:表示可以选择将这个字符包含在子序列中(加上dp[i-1][j-1]
)或者不包含(加上dp[i-1][j]
)。
- 如果不相等:
dp[i][j] = dp[i - 1][j]
:只能选择不包含s[i-1]
。
- 外层循环遍历
- 结果
- 返回
dp[s.size()][t.size()]
,即s
中包含t
的不同子序列的数量。
- 返回
代码:
class Solution {
public:
int numDistinct(string s, string t) {
int sLen = s.size(), tLen = t.size();
vector<vector<uint64_t>> dp(sLen + 1, vector<uint64_t>(tLen + 1));
for(int i = 0; i < sLen; ++i) dp[i][0] = 1;
for(int j = 1; j < tLen; ++j) dp[0][j] = 0;
for(int i = 1; i <= sLen; ++i) {
for(int j = 1; j <= tLen; ++j) {
if(s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
else dp[i][j] = dp[i - 1][j];
}
}
return dp[sLen][tLen];
}
};
583. 两个字符串的删除操作
题目链接:https://leetcode.cn/problems/delete-operation-for-two-strings/
文章讲解:https://programmercarl.com/0583.两个字符串的删除操作.html
题目难度:中等
视频讲解:https://www.bilibili.com/video/BV1we4y157wB/
题目状态:看题解
思路:
维护一个二维动规数组dp[i][j]
用来表示将word1
的前i
个字符转换为word2
的前j
个字符所需的最小操作次数。
初始化dp[i][j]
:
dp[i][0] = i
:将word1
的前i
个字符转换为空字符串需要i
次删除操作。dp[0][j] = j
:将空字符串转换为word2
的前j
个字符需要j
次插入操作。
更新动规数组:
对于每一对i
和j
,我们考虑以下两种情况:
- 字符匹配(
word1[i-1] == word2[j-1]
):- 如果当前字符相同,不需要任何操作:
dp[i][j] = dp[i - 1][j - 1];
- 如果当前字符相同,不需要任何操作:
- 字符不匹配(
word1[i-1] != word2[j-1]
):- 我们可以进行两种操作:
- 删除一次
word1
的元素:此时需要dp[i - 1][j] + 1
次操作次数。 - 删除一次
word2
的元素:此时需要dp[i][j - 1] + 1
此操作次数。
- 删除一次
- 取这两种操作的最小值:
min(dp[i - 1][j] + 1, dp[i][j - 1] + 1)
- 我们可以进行两种操作:
代码:
class Solution {
public:
int minDistance(string word1, string word2) {
int len1 = word1.size(), len2 = word2.size();
vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1));
for(int i = 0; i <= len1; ++i) dp[i][0] = i;
for(int j = 0; j <= len2; ++j) dp[0][j] = j;
for(int i = 1; i <= len1; ++i) {
for(int j = 1; j <= len2; ++j) {
if(word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
else dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
}
}
return dp[len1][len2];
}
};
72. 编辑距离
题目链接:https://leetcode.cn/problems/edit-distance/
文章讲解:https://programmercarl.com/0072.编辑距离.html
题目难度:中等
视频讲解:https://www.bilibili.com/video/BV1qv4y1q78f/
题目状态:有思路,细节出了问题
思路:
这道题的本质就是在上道题的基础上做了改变,上道题遇到不相等的字符时只需要考虑删除操作,这道题在遇到不相等的字符时需要考虑三种情况:删除、插入、替换。
- 删除:在
word1
中删除一个字符,也就转化为了word1[i - 2]
与word2[j - 1]
相比较了,因此dp[i][j] = dp[i - 1][j] + 1
。 - 插入:在
word1
中添加一个字符,其实这个操作得到的最终结果和在word2
中删除一个字符的结果是一样的,因此就转化为word1[i - 1]
与word2[j - 2]
相比较了,因此dp[i][j] = dp[i][j - 1] + 1
。 - 替换:替换操作就是在
word1[i - 1] != word2[j - 1]
的前提下进行一次操作使得word1[i - 1] == word2[j - 1]
,因此dp[i][j] = dp[i - 1][j - 1] + 1
。
最终取这三个操作的最小值即可。
代码:
class Solution {
public:
int minDistance(string word1, string word2) {
int len1 = word1.size(), len2 = word2.size();
vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1));
for(int i = 0; i <= len1; ++i) dp[i][0] = i;
for(int j = 0; j <= len2; ++j) dp[0][j] = j;
for(int i = 1; i <= len1; ++i) {
for(int j = 1; j <= len2; ++j) {
if(word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
else dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
}
}
return dp[len1][len2];
}
};
标签:part12,第三十九,随想录,int,word1,https,word2,dp,size
From: https://www.cnblogs.com/frontpen/p/18360135