思路

插入、删除、替换的最少代价，长度上界与空串边界。

参考程序（C++11）

#include <bits/stdc++.h>
using namespace std;
int main(){string a,b;getline(cin,a);getline(cin,b);if(!a.empty()&&a.back()=='\r')a.pop_back();if(!b.empty()&&b.back()=='\r')b.pop_back();vector<vector<int>>d(a.size()+1,vector<int>(b.size()+1));for(int i=0;i<=(int)a.size();i++)d[i][0]=i;for(int j=0;j<=(int)b.size();j++)d[0][j]=j;for(int i=1;i<=(int)a.size();i++)for(int j=1;j<=(int)b.size();j++)d[i][j]=min({d[i-1][j]+1,d[i][j-1]+1,d[i-1][j-1]+(a[i-1]!=b[j-1])});cout<<d[a.size()][b.size()]<<'\n';}