目录
115不同的子序列
- dp数组的含义:dp[i][j]以 i-1结尾的s中包含有多少个以j-1为结尾的t
- dp初始化:dp[0][0]空字符串中有多少个空字符串,显然1个 dp[i][0]以i-1为结尾的s中包含有多少个空字符串,也是1个
- 递推公式: 显然需要考虑 s[i-1]==t[j-1]
- s[i-1]t[j-1] dp[i][j]=dp[i-1][j-1]+dp[i-1][j],因为也需要考虑到前面的dp数组已经满足条件
比如bagg和bag s[3]t[2]可以通过bag ba推导出一个满足的,也要加入bag bag来推导 - s[i-1]!=t[j-1] dp[i][j]=dp[i-1][j]
class Solution {
public:
int numDistinct(string s, string t) {
//dp数组的含义dp[i][j]以 i-1结尾的s中包含有多少个以j-1为结尾的t
int n=s.length();
int m=t.length();
vector<vector<long long>> dp(n+1,vector<long long>(m+1,0));
for(int i=0;i<=n;i++)
{
dp[i][0]=1;
}
for(int i=1;i<=m;i++)
{
dp[0][i]=0;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(s[i-1]==t[j-1])
{
dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%1000000007;
}
else{
dp[i][j]=dp[i-1][j];
}
}
}
return dp[n][m];
}
};
583. 两个字符串的删除操作
主要是递推公式
- 如果字符相等,那么dp[i][j]=dp[i-1][j-1]
- 如果不等
- 删word1,即把当前word1[i]给删了,dp[i][j]=dp[i-1][j]+1
- 删word2,dp[i][j]=dp[i][j-1]+1
class Solution {
public:
int minDistance(string word1, string word2) {
int n = word1.length();
int m = word2.length();
// dp含义,以i-1为结尾的word1变到以j-1为结尾的word2需要的操作步数
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
// dp初始化
//显然,从长度为x的字符串,变成长度为0的字符串,需要删除x个字符
for (int i = 0; i <= n; i++) {
dp[i][0] = i;
}
for (int j = 0; j <= m; j++) {
dp[0][j] = j;
}
// dp推导
// word1[i]==word2[j] 挺好,不用变了,dp[i][j]=dp[i-1][j-1]
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; 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[n][m];
}
};
编辑距离
题目的初始化和dp定义和之前的题目都差不多
主要是递推公式中不相等的情况
当word1[i]!=word2[j]时
dp[i][j]=以下三个中的最小值
- dp[i-1][j-1]+1代表换了一个元素,比如bag bae 只要替换一下就能得到相同的元素
- dp[i-1][j]+1 代表删了word1[i-1]元素
- dp[i][j-1]+1 代表删了word2[j-1]元素
class Solution {
public:
int minDistance(string word1, string word2) {
//dp[i][j]:以i-1为结尾的字符串word1,和以j-1位结尾的字符串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],min(dp[i][j-1],dp[i-1][j-1]))+1;
}
}
}
return dp[word1.size()][word2.size()];
}
};
标签:结尾,int,编辑,最终版,word1,word2,字符串,动态,dp
From: https://www.cnblogs.com/liviayu/p/17979653