编辑距离问题.txt

动态规划解一系列经典问题

int dist()
{
int m=a.size();
int n=b.size();
vector<int>d(n+1,0);
for(int i=1;i<=n;i++)
d[i]=i;
for(i=1;i<=m;i++)
{
int y=i-1;
for(int j=1;i<=n;j++)
{
int x=y;
y=d[j];
int z=j>1?d[j-1]:i;
int del=a[i-1]==b[j-1]?0:1;
d[j]=min(x+del,y+1,z+1);
}
}
return d[n];
}