583.?兩個字符串的刪除操作?

動規(guī)五部曲

確定dp數(shù)組（dp table）以及下標(biāo)的含義

dp[i][j]：以i-1為結(jié)尾的字符串word1，和以j-1位結(jié)尾的字符串word2，想要達(dá)到相等，所需要刪除元素的最少次數(shù)

確定遞推公式

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數(shù)組初始化

dp[i][0]：word2為空字符串，以i-1為結(jié)尾的字符串word1要刪除i個元素，和word2相同，dp[i][0] = i。

dp[0][j]=j

確定遍歷順序

遍歷的時候從上到下，從左到右

舉例推導(dǎo)dp數(shù)組

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.?編輯距離

動規(guī)五部曲

確定dp數(shù)組（dp table）以及下標(biāo)的含義

dp[i][j] 表示以下標(biāo)i-1為結(jié)尾的字符串word1，和以下標(biāo)j-1為結(jié)尾的字符串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數(shù)組初始化

dp[i][j] 表示以下標(biāo)i-1為結(jié)尾的字符串word1，和以下標(biāo)j-1為結(jié)尾的字符串word2，最近編輯距離為dp[i][j]。

dp[i][0] ：以下標(biāo)i-1為結(jié)尾的字符串word1，和空字符串word2，最近編輯距離為dp[i][0]。

那么dp[i][0]就應(yīng)該是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;}}}

舉例推導(dǎo)dp數(shù)組