代码随想录算法训练营第五十八天|583. 两个字符串的删除操作、

583. 两个字符串的删除操作 

动规五部曲

确定dp数组（dp table）以及下标的含义

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] dp[i - 1][j] + 1

删word2[j - 1] dp[i][j - 1] + 1

同时删word1[i - 1]和word2[j - 1]   dp[i - 1][j - 1] + 2

dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});

dp数组初始化

dp[i][0]：word2为空字符串，以i-1为结尾的字符串word1要删除i个元素，和word2相同，dp[i][0] = i。

dp[0][j]=j

确定遍历顺序

遍历的时候从上到下，从左到右

举例推导dp数组

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数组（dp table）以及下标的含义

dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。

确定递推公式

word1[i - 1] == word2[j - 1] 不用编辑  dp[i][j] = dp[i - 1][j - 1]

word1[i - 1] != word2[j - 1]  

word1删除一个元素  dp[i][j] = dp[i - 1][j] + 1;

word2删除一个元素 dp[i][j] = dp[i][j - 1] + 1;

替换元素，word1替换word1[i - 1]，使其与word2[j - 1]相同 dp[i][j] = dp[i - 1][j - 1] + 1;

dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;

dp数组初始化

dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。

dp[i][0] ：以下标i-1为结尾的字符串word1，和空字符串word2，最近编辑距离为dp[i][0]。

那么dp[i][0]就应该是i，对word1里的元素全部做删除操作，即：dp[i][0] = i;

同理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;}}}

举例推导dp数组