115.不同的子序列
题目链接：代码随想录
解题思路
1.dp[i][j] 为在s的前i个元素(即s[0, i - 1])(以i-1结尾)中，有多少个t[0, j - 1]匹配(以t[j - 1]为结尾)
2.递推公式
//如果当前元素相等了，求s[0,i-2]中有多少个t[0,j-2] + 前面有多少个完整的t[0,j-1]
以"bag"举例 s前面有多少"ba" + 前面有多少个"bag"
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][j] = dp[i-1][j] //模拟删除了i-1这个元素
//如果当前元素不相等了，那么就之前看s[0,i-2]中有多少个t[0,j-1]
还是"bag"为例，那么就求s里面有多少个"bag"
3.初始化
当t为空字符串 dp[i][0] = 1 s中有一个空字符串
当s为空字符串 dp[0][j] = 0
dp[0][0] = 1 都为空字符串
4.遍历顺序
从前往后，结果在s.size()和t.size()中
class Solution {
private:
const long long mod = 10e9+7;
public:
int numDistinct(string s, string t) {
vector<vector<long>> dp(s.size()+1,vector<long>(t.size()+1,0));
for(int i = 0 ;i <=s.size() ; i++)
{
dp[i][0] = 1 ;
}
for(int j = 0 ; j<=t.size() ; j++)
{
dp[0][j] = 0;
}
dp[0][0] = 1; //都为空字符串
for(int i =1 ;i <=s.size() ; i++)
{
for(int j = 1 ; j<=t.size() ; j++)
{
//如果当前字符都相同，那么就去看前面[0,i-2]有没有[0,j-2]
//同时也可以不使用这个字符，去判断前面有没有[0,j-1]
if(s[i-1]==t[j-1]) dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % mod;
//如果不相同，就相当于删除这个字符，看前面的
else dp[i][j] = dp[i-1][j] % mod;
}
}
//最后结果肯定是在结尾，因为是个区间
return dp[s.size()][t.size()];
}
};583. 两个字符串的删除操作
题目链接：代码随想录
视频讲解：动态规划之子序列，还是为了编辑距离做铺垫 | LeetCode：583.两个字符串的删除操作_哔哩哔哩_bilibili
解题思路
这题是两个字符串都可以删
1.dp[i][j] 需要比较两个字符串的长度，因此需要二维数组
以i-1为结尾的word1([0,i-1])，以j-1为结尾的word2([0,j-1])的最小操作数
2.递推公式
当前元素相等，那么就不需要操作，那么就和[0,i-2]和[0,j-2]的操作数
if(word1[i-1] == word2[j-1] ) dp[i][j] = dp[i-1][j-1]
元素不相等了，此时要进行删除操作
有三种情况，删word1 删word2 (先word1，再删word2，就是都删了的情况)
else dp[i][j] = min (dp[i-1][j] + 1 , dp[i][j-1] + 1) //取最小的操作数
3.初始化
dp[0][j] = j; dp[i][0] = i; 第一列第一行，面对空字符串，那么有多少个元素，就要操作多少次
4.递推公式
从左到右，从上到下
class Solution {
public:
int minDistance(string word1, string word2) {
vector<vector<int>> dp(word1.size()+1 , vector<int>(word2.size()+1 , 0));
//当word2为空字符串
for(int i = 0 ; i<=word1.size() ; i++)
{
dp[i][0] = i; //有多少个字符就删几个
}
//word1为空字符串
for(int j =0 ; j<=word2.size() ; j++)
{
dp[0][j] = j ; //有多少个就删几次
}
for(int i =1 ; i<=word1.size(); i++)
{
for(int j = 1; j<=word2.size() ; 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[word1.size()][word2.size()];
}
};72. 编辑距离
题目链接：代码随想录
解题思路
1.dp[i][j] 以i-1结尾的word1([0,i-1])，以j-1为结尾的word2([0,j-1])的最小操作次数
2.递推公式
//如果元素相同
if(word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1] //元素相同，那么就不需要操作
如果不相同
我们有增，删，替换三种操作
删一个元素 dp[i][j] = dp[i-1][j] + 1; //操作word1删除当前元素，次数+1
增一个元素 （逆向考虑，word1增加一个元素，相当于word2减去一个元素的操作次数是一样的）
dp[i][j] = dp[i][j-1] + 1;
替换一个元素 dp[i][j] = dp[i-1][j-1] + 1 //替换后，我们i-1位置的元素相同了，再做一个+1的操作
else 这三种取最小值即可
3.初始化
dp[i][0] = i ; dp[0][j] = j; //其中一个有空字符串，那么有多少个元素就操作多少次
4.遍历顺序
从左到右，从上到下
class Solution {
public:
int minDistance(string word1, string word2) {
vector<vector<int>> dp(word1.size()+1 , vector<int>(word2.size()+1,0));
for(int i = 0 ;i<=word1.size() ; i++) dp[i][0] = i;
for(int j = 0 ;j<=word2.size() ; j++) dp[0][j] = j;
for(int i =1 ;i<= word1.size(); i++)
{
for(int j =1 ; j<=word2.size(); 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 , min(dp[i][j-1]+1 , dp[i-1][j-1]+1));
}
}
return dp[word1.size()][word2.size()];
}
};