代码随想录算法训练营第四十五天|动态规划part12

 定义dp[i][j]表示 s 0-i-1与t 0-j-1不同的子序列的个数

以s=batgtg t=bag为例子

s【4】！=t【3】

所以dp[5][4]=dp[4][4]        也就是不考虑s[4]

继续往后

s[5]==t[3]

也就是s[5]跟t【3】配对上了 

batgt 与bag配对的个数加上 batgt与ba配对的个数

dp[6][4]=dp[5][4]+dp[5][3]

错误解答：

class Solution {
public:int numDistinct(string s, string t) {vector<vector<int>>dp(s.size()+1,vector<int>(t.size()+1,0));for(int i=1;i<s.size();i++){for(int j=1;j<t.size();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[s.size()][t.size()];}
};

上面算出来的结果都是0，原因是错误地初始化。

正确解答：

class Solution {
public:int numDistinct(string s, string t) {vector<vector<unsigned int>>dp(s.size()+1,vector<unsigned int>(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++){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[s.size()][t.size()];}
};

int 32位

long  64位

思路：

1.定义dp数组定义

dp[i][j]表示使以i-1结尾的word1和以j-1为结尾的word2相同所需要的删除步骤

2.状态转移方程

if(word1[i-1]==word2[j-1]){

dp[i][j]=dp[i-1][j-1]   //不同考虑这两个字母

}else{

int a=min（dp[i-1][j]+1,dp[i][j-1]+1）  //删除word1或word2

dp[i][j]=min（a,dp[i-1][j-1]+2）       //两个都删除

}

3.初始化dp[i][0]与dp[0][j]

dp[i][0]=i;

dp[0][j]=j;

dp[0][0]=0;

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{int a=min(dp[i-1][j]+1,dp[i][j-1]+1);dp[i][j]=min(a,dp[i-1][j-1]+2)    ;   //两个都删除}}}return dp[word1.size()][word2.size()];}
};

class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>>dp(word1.size()+1,vector<int>(word2.size()+1,0));//定义dp【i】【j】word1以i-1结尾word2以j-1结尾的最少操作数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{int erase=min(dp[i-1][j]+1,dp[i][j-1]+1);//删除或增加dp[i][j]=min(erase,dp[i-1][j-1]+1) ;      //替换}}}return dp[word1.size()][word2.size()];}
};

 动态规划解这个太棒了

关键是递推公式的推导。