移动做网站吗,如何选择个人网站主题,桐乡网站建设,邯郸网站建设选哪家好583. 两个字符串的删除操作 题目链接/文章讲解/视频讲解#xff1a;代码随想录 1.代码展示
//583.两个字符串的删除操作
int minDistance(string word1, string word2) {//step1 构建dp数组#xff0c;dp[i][j]的含义是要使以i-1为结尾的word1和以j-1为结尾的word2//删除其元…583. 两个字符串的删除操作 题目链接/文章讲解/视频讲解代码随想录 1.代码展示
//583.两个字符串的删除操作
int minDistance(string word1, string word2) {//step1 构建dp数组dp[i][j]的含义是要使以i-1为结尾的word1和以j-1为结尾的word2//删除其元素后相同所需最小的删除步数vectorvectorint dp(word1.size() 1, vectorint(word2.size() 1, 0));//step2 状态转移方程//if (word1[i - 1] word[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, dp[i - 1][j - 1] 2);//对应着三种情况删除word1[i - 1]或者word2[j - 1]或者同时删除//step3 初始化for (int i 0; i word1.size(); i) {dp[i][0] i;}for (int j 0; j word2.size(); j) {dp[0][j] j;}//step4 开始遍历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 {dp[i][j] min({ dp[i - 1][j] 1, dp[i][j - 1] 1, dp[i - 1][j - 1] 2 });}}}return dp[word1.size()][word2.size()];
}
2.本题小节 思考 首先明确dp[i][j]的含义是下标以i-1为结尾的word1和以下标为j-1结尾的word2删除元素相等所需的最少步骤。当word1[i - 1] word2[j - 1]时此时不需要删除元素因此dp[i][j] dp[i - 1][j - 1]当不相等时此时既可以删除word1下标i-1处的元素对应的是dp[i - 1][j] 1也可以删除word2下标j-1处的元素对应的是dp[i][j-1] 1也可以是同时删除掉对应的是dp[i - 1][j - 1] 2因此dp[i][j]从上面三种情况中选择最小的。初始化时要注意dp[i][0]对应的位置初始化为idp[0][j]对应位置初始化为j这个很好想。 步骤注意思考的内容按照步骤来即可。
72. 编辑距离 题目链接/文章讲解/视频讲解代码随想录 1.代码展示
//72.编辑距离
int minDistance(string word1, string word2) {//step1 构建dp数组dp[i][j]的含义是要使以i-1为结尾的word1和以j-1为结尾的word2//相同需要操作增加、删减、替换的次数vectorvectorint dp(word1.size() 1, vectorint(word2.size() 1, 0));//step2 状态转移方程//if (word1[i - 1] word[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, dp[i - 1][j - 1] 1);//对应着三种情况删掉word1[i - 1](删除),删掉word2[j - 1](增加)替换//step3 初始化for (int i 0; i word1.size(); i) {dp[i][0] i;}for (int j 0; j word2.size(); j) {dp[0][j] j;}//step4 开始遍历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 {dp[i][j] min({ dp[i - 1][j] 1, dp[i][j - 1] 1, dp[i - 1][j - 1] 1 });}}}return dp[word1.size()][word2.size()];
}
2.本题小节 思考dp[i][j]的含义是以下标i-1为结尾的word1通过增加删除替换能够变成以下标j-1为结尾的word2所需要的最小步骤。当word1[i - 1] word2[j - 1]时此时不需要操作则dp[i][j] dp[i - 1][j - 1]当不相等时可以通过删除删除word1[i - 1]、增加(删除word2[j - 1])、和替换word1[i - 1]替换为word[j - 1]来操作分别对应的时dp[i - 1][j] 1、dp[i][j - 1] 1、dp[i - 1][j - 1] 1选择最小情况初始化和上题一样。 基本步骤根据思考和动态规划的步骤来即可。 编辑距离总结代码随想录
