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数组
