力扣算法刷题 Day 45

115 不同的子序列题目链接添加链接描述思路dp五部曲dp数组含义dp[i][j]表示s1下标从0到i-1和s2下标从0到j-1的匹配的字符串个数递推: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]初始化dp[0][j] 1,dp[i][0] 0, dp[0][0] 1遍历顺序从上到下从左到右举例推导文章详解添加链接描述classSolution{public:intnumDistinct(string s,string t){vectorvectoruint64_tdp(s.size()1,vectoruint64_t(t.size()1));for(inti0;is.size();i)dp[i][0]1;for(intj1;jt.size();j)dp[0][j]0;for(inti1;is.size();i){for(intj1;jt.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五部曲dp数组含义dp[i][j]表示从dp[i-1]到dp[j-1]所需的最小步数递推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);初始化dp[i][0] i, dp[0][j] j;遍历顺序从上到下从左到右模拟文章详解添加链接描述classSolution{public:intminDistance(string word1,string word2){vectorvectorintdp(word1.size()1,vectorint(word2.size()1));for(inti0;iword1.size();i)dp[i][0]i;for(intj0;jword2.size();j)dp[0][j]j;for(inti1;iword1.size();i){for(intj1;jword2.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五部曲dp数组含义dp[i][j]表示s下标0到i-1和t下标0到j-1所需的最小操作数递推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初始化dp[i][0] i,dp[0][j] j遍历顺序从上到下从左到右模拟文章详解添加链接描述classSolution{public:intminDistance(string word1,string word2){vectorvectorintdp(word1.size()1,vectorint(word2.size()1,0));for(inti0;iword1.size();i)dp[i][0]i;for(intj0;jword2.size();j)dp[0][j]j;for(inti1;iword1.size();i){for(intj1;jword2.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()];}};