力扣算法刷题 Day 45

115 不同的子序列

题目链接

添加链接描述

思路

dp五部曲：

1. dp数组含义：dp[i][j]表示s1下标从0到i-1和s2下标从0到j-1的匹配的字符串个数
2. 递推:if(s1[i-1] == s2[j-1]) dp[i][j] = dp[i-1][j-1] + dp[i-1][j]; else dp[i][j] = dp[i-1][j]
3. 初始化：dp[0][j] = 1,dp[i][0] = 0, dp[0][0] = 1
4. 遍历顺序：从上到下，从左到右
5. 举例推导：

文章详解

添加链接描述

classSolution{public:intnumDistinct(string s,string t){vector<vector<uint64_t>>dp(s.size()+1,vector<uint64_t>(t.size()+1));for(inti=0;i<s.size();i++)dp[i][0]=1;for(intj=1;j<t.size();j++)dp[0][j]=0;for(inti=1;i<=s.size();i++){for(intj=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];}}}returndp[s.size()][t.size()];}};

583 两个字符串的删除操作

题目链接

添加链接描述

思路

dp五部曲：

1. dp数组含义：dp[i][j]表示从dp[i-1]到dp[j-1]，所需的最小步数
2. 递推：`if(dp[i-1] == dp[j-1]) dp[i][j] = dp[i-1][j-1]; else dp[i][j] = dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
3. 初始化：dp[i][0] = i, dp[0][j] = j;
4. 遍历顺序：从上到下，从左到右
5. 模拟：

文章详解

添加链接描述

classSolution{public:intminDistance(string word1,string word2){vector<vector<int>>dp(word1.size()+1,vector<int>(word2.size()+1));for(inti=0;i<=word1.size();i++)dp[i][0]=i;for(intj=0;j<=word2.size();j++)dp[0][j]=j;for(inti=1;i<=word1.size();i++){for(intj=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);}}}returndp[word1.size()][word2.size()];}};

72 编辑距离

题目链接

添加链接描述

思路

dp五部曲：

1. dp数组含义：dp[i][j]表示s下标0到i-1和t下标0到j-1所需的最小操作数
2. 递推：if(s[i] == t[j]) dp[i][j] = dp[i-1][j-1]；else dp[i][j] = min(dp[i][j-1] + 1,dp[i-1][j] + 1,dp[i-1][j-1] + 1
3. 初始化：dp[i][0] = i,dp[0][j] = j
4. 遍历顺序：从上到下从左到右
5. 模拟：

文章详解

添加链接描述

classSolution{public:intminDistance(string word1,string word2){vector<vector<int>>dp(word1.size()+1,vector<int>(word2.size()+1,0));for(inti=0;i<=word1.size();i++)dp[i][0]=i;for(intj=0;j<=word2.size();j++)dp[0][j]=j;for(inti=1;i<=word1.size();i++){for(intj=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-1][j],dp[i][j-1]})+1;}}}returndp[word1.size()][word2.size()];}};