思路：f[i][j]表示a1…ai变成b1…bj所需的最小操作数，每次更新f[i][j]都是看a[i]如何操作，如果a[i]需要删除那么说明a1…ai-1已经和b1…bj已经相同了那么f[i][j]=f[i-1][j]+1，如果a[i]处需要增加说明a1…ai和b1…bj-1相同f[i][j]=f[i][j-1]+1，如果需要修改a[i]变成b[j]那么说明a1…ai-1与b1…bj-1相同f[i][j]=f[i-1][j-1]+1
代码：
class Solution {
public:
int minDistance(string word1, string word2) {
int n=word1.size();
int m=word2.size();
word2=' '+word2;
word1=' '+word1;
vector> f(n+1,vector(m+1));
for(int i=0;i<=n;i++) f[i][0]=i;
for(int i=0;i<=m;i++) f[0][i]=i;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
f[i][j]=min(f[i-1][j],f[i][j-1])+1;
int t=word1[i]!=word2[j];
f[i][j]=min(f[i][j],f[i-1][j-1]+t);
}
}
return f[n][m];
}
};
