题目：编辑距离 。
思路
显然，定义 \(f[i][j]\) 表示字符串 \(a\) 中前 \(i\) 个字符到 字符串 \(b\) 中前 \(j\) 个字符的编辑距离。
那么对于 \(a_i=b_j\) 时，我们对当前位无需进行任何编辑操作，则 \(f[i][j]=f[i-1][j-1]\) 。
如果 \(a_i \ne b_j\) ，那么我们就要对当前位进行编辑：
- 对于修改操作，我们先要保证 字符串 \(a\) 中前 \(i-1\) 个字符 已经编辑到了 字符串 \(b\) 中前 \(j-1\) 个字符，接下来才把 \(a_i\) 修改成 \(b_j\) ，所以转移为 \(f[i][j]=f[i-1][j-1]+1\) 。
- 对于插入操作，因为我们是向 \(a_i\) 后面插入一个 \(b_j\) ，所以我们要保证 字符串 \(a\) 中前 \(i\) 个字符 已经编辑到了 字符串 \(b\) 中前 \(j-1\) 个字符，再同时往这两个字符串后插一个 \(b_j\) ，所以转移为 \(f[i][j]=f[i][j-1]+1\) 。
- 对于删除操作，由于我们是删除 \(a_i\) 字符，所以我们要保证 字符串 \(a\) 中前 \(i-1\) 个字符 已经编辑到了 字符串 \(b\) 中前 \(j\) 个字符，这样才能删掉 \(a_i\) ，所以方程为 \(f[i][j]=f[i-1][j]+1\) 。
这三种情况取一个 min 即可。
注意初始化，\(f[0][0]=0,f[i][0]=i,f[0][j]=j\) ，因为分别要进行这么多次的删除和插入。
#include <bits/stdc++.h>
using namespace std;
string a,b;
int f[2005][2005];
int main()
{
cin>>a>>b;
memset(f,0x3f,sizeof(f));
f[0][0]=0;
for(int i=1;i<=a.length();i++)f[i][0]=i;
for(int i=1;i<=b.length();i++)f[0][i]=i;
for(int i=1;i<=a.length();i++)
{
for(int j=1;j<=b.length();j++)
{
if(a[i-1]==b[j-1])f[i][j]=f[i-1][j-1];
else f[i][j]=min(f[i][j],min(f[i-1][j-1]+1,min(f[i-1][j]+1,f[i][j-1]+1)));
}
}
cout<<f[a.length()][b.length()];
return 0;
}