https://leetcode-cn.com/problems/edit-distance/
class Solution {
public:
int minDistance(string word1, string word2) {
int n = word1.length();
int m = word2.length();
int cost;
vector<vector<int>> dp(n+1,vector<int>(m+1));
// for(int i=1;i<=3;i++){
// for(int j=1;j<=3;j++){
// printf("%d ",dp[i][j]);
/// }
// printf("\n");
// }
for(int i=0;i<=n;i++)dp[i][0]=i;
for(int i=0;i<=m;i++)dp[0][i]=i;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dp[i][j] = min(dp[i-1][j],dp[i][j-1])+1;//删除和插入
if(word1[i-1]==word2[j-1])
{
dp[i][j] = min(dp[i][j],dp[i-1][j-1]);//skip
}
else{
dp[i][j] = min(dp[i][j],dp[i-1][j-1]+1);//替换
}
}
}
return dp[n][m];
}
};