583.?兩個(gè)字符串的刪除操作?
動(dòng)規(guī)五部曲
確定dp數(shù)組（dp table）以及下標(biāo)的含義
dp[i][j]：以i-1為結(jié)尾的字符串word1讯泣，和以j-1位結(jié)尾的字符串word2纫普，想要達(dá)到相等，所需要?jiǎng)h除元素的最少次數(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
同時(shí)刪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要?jiǎng)h除i個(gè)元素昨稼，和word2相同，dp[i][0] = i拳锚。
dp[0][j]=j
確定遍歷順序
遍歷的時(shí)候從上到下假栓，從左到右
舉例推導(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.?編輯距離
動(dòng)規(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刪除一個(gè)元素??dp[i][j] = dp[i - 1][j] + 1;
word2刪除一個(gè)元素?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构罗，對(duì)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ù)組
