沽源网站建设案例,烟台理工学校网站,网站建设配色方案,wordpress默认中文1 583. 两个字符串的删除操作
583. 两个字符串的删除操作
【注意点1】感觉和下面这题很像。就是一模一样#xff0c;return变一下就是。
1143. 最长公共子序列
【注意点2】注意这题和day55的最后一题的区别#xff0c;本题求的是最大长度#xff0c;那题求的是组合方式。…1 583. 两个字符串的删除操作
583. 两个字符串的删除操作
【注意点1】感觉和下面这题很像。就是一模一样return变一下就是。
1143. 最长公共子序列
【注意点2】注意这题和day55的最后一题的区别本题求的是最大长度那题求的是组合方式。
AC代码
class Solution {
public:int dp[510][510]; // word1的前i-1的字符串 与 word2的前i-1的字符串的最长公共子序列长度/*if(word1[i-1] word2[j-1])dp[i][j] dp[i-1][j-1] 1;elsedp[i][j] max(dp[i][j-1],dp[i-1][j]);dp[0][0] 0dp[i][0] 0dp[0][j] 0i j模拟——*/int minDistance(string word1, string word2) {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] 1;elsedp[i][j] max(dp[i][j-1],dp[i-1][j]);}}return word1.size() word2.size() - 2*dp[word1.size()][word2.size()];}
};
2 72. 编辑距离
72. 编辑距离
状态转移方程难推导。学习题解的详见注释
AC代码
class Solution {
public:int dp[510][510]; // word1的前i-1个的子串 转换成 word2的前j-1个的子串最小操作数/*if(word1[i-1] word2[j-1]){dp[i][j] dp[i-1][j-1]; //不用操作}else{//【1】 插入按照题解的说法 一个子串删除最后一个元素 等价于 另一个子串增加最后一个元素所以省去// 【2】 删除删掉word1[i-1]dp[i][j] dp[i-1][j] 1;删掉word2[j-1]dp[i][j] dp[i][j-1] 1;// 【3】 替换dp[i][j] dp[i-1][j-1] 1;}初始化dp[0][0] 0;dp[0][j] j;dp[i][0] i;顺序i j模拟*/int minDistance(string word1, string word2) {for(int j 0; j word2.size();j)dp[0][j] j;for(int i 0; i word1.size();i)dp[i][0] i;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]; //不用操作elsedp[i][j] min(dp[i-1][j],min(dp[i][j-1] , dp[i-1][j-1])) 1;return dp[word1.size()][word2.size()];}
};
编辑距离系列总结
go to
