网站颜色 字体员工培训

115.不同的子序列

题目
dp[i][j]表示的是在以是s[j]为结尾的字符串中最多可以找到几种组成以t[i]为结尾的字符串的方式。
如果s[i]==t[j]，
1.利用第i个和第j个匹配，在j-1中寻找i-1.
2.不适用这两个进行匹配，在j-1中寻找i
如果s[i]！=t[j]
则只能在j-1中寻找i

 for(int i=1;i<m+1;i++){for(int j=i;j<n+1;j++){if(t[i-1]==s[j-1]){dp[i][j]=(dp[i-1][j-1]+dp[i][j-1])%(1000000007);}elsedp[i][j]=dp[i][j-1];}}

完整代码：

class Solution {
public:int numDistinct(string s, string t) {int m=t.size();int n=s.size();vector<vector<int>> dp(m+1,vector<int>(n+1,0));for(int j=0;j<n+1;j++)dp[0][j]=1;for(int i=1;i<m+1;i++){for(int j=i;j<n+1;j++){if(t[i-1]==s[j-1]){dp[i][j]=(dp[i-1][j-1]+dp[i][j-1])%(1000000007);}elsedp[i][j]=dp[i][j-1];}}return dp[m][n];}
};

583. 两个字符串的删除操作

方法一

找出两个字符串的最长公共子序列，然后用两个字符串的长度之和减去2*dp[m][n]

方法二

dp[i][j]代表以word1[i]和word2[j]为结尾的字符串删成相同的字符串需要的最小步数
if(word1[i]==word2[j]){
dp[i][j]=dp[i-1][j-1];
}
else{
dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);
//分别删除第i个和第j个后剩余字符串的最小步数，再加上前面删除的一个步数。
}

class Solution {
public:int minDistance(string word1, string word2) {int m=word1.size();int n=word2.size();vector<vector<int>> dp(m+1,vector<int>(n+1,0));for(int i=1;i<m+1;i++){dp[i][0]=i;}for(int j=1;j<n+1;j++)dp[0][j]=j;for(int i=1;i<m+1;i++){for(int j=1;j<n+1;j++){if(word1[i-1]==word2[j-1]){dp[i][j]=dp[i-1][j-1];}elsedp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);//分别删除第i个和第j个后剩余字符串的最小步数，再加上前面删除的一个步数。}}return dp[m][n];}
};

72. 编辑距离

如果word1[i]和word2[j]不相同，有三种方式：
1.修改第i个使他与j相同，要dp[i-1][j-1]+1步
2.删除第i个，要dp[i-1][j]+1
3.删除第j个，要dp[i][j-1]+1

插入一个和另一个相等的字符和删除另一个的步数一样，所以可以只用讨论删除的。

if(word1[i-1]!=word2[j-1]){	dp[i][j]=min（dp[i-1][j-1]+1，min（dp[i-1][j]+1，dp[i][j-1]+1）;
}
elsedp[i][j]=dp[i-1][j-1];

注意：是i-1和j-1，因为i的长度比m多一个。

完整代码：

class Solution {
public:int minDistance(string word1, string word2) {int m=word1.size();int n=word2.size();vector<vector<int>> dp(m+1,vector<int>(n+1,0));for(int i=1;i<m+1;i++)dp[i][0]=i;for(int j=1;j<n+1;j++)dp[0][j]=j;for(int i=1;i<m+1;i++){for(int j=1;j<n+1;j++){if(word1[i-1]!=word2[j-1]){	dp[i][j]=min(dp[i-1][j-1]+1,min(dp[i-1][j]+1,dp[i][j-1]+1));}elsedp[i][j]=dp[i-1][j-1];}}return dp[m][n];}
};