经典DP，给定两个字符串x和y，求少的修改次数将x变成y。修改的规则只能是如下三种之一：
删除、插入、改变。同理，用a[i][j]表示把x的前i个字符变成y的前j个字符所需的最少操作次数，则状态转移方程为：
当x[i]==y[j]时：a[i][j] = min(a[i-1][j-1],a[i-1][j]+1,a[i][j-1]+1);
当x[i]!=y[j]时：a[i][j] = min(a[i-1][j-1],a[i-1][j],a[i][j-1])+1;
最后注意一下边界条件，DP的边界条件是必不可少的。
#include <stdio.h>
#include <string.h>
#define N 1005
#define MIN(a, b) (a < b ? a : b)
#define MAX(a, b) (a > b ? a : b)
int a[N][N];
char s1[N], s2[N];
int main()
{
int l1, l2;
while(~scanf("%d %s", &l1, &s1))
{
scanf("%d %s", &l2, &s2);
memset(a, 0, sizeof(a));
for(int i = 0; i < l1; i++)
{
a[0][i + 1] = i + 1;
}
for(int i = 0; i < l2; i++)
{
a[i + 1][0] = i + 1;
}
for(int i = 0; i < l2; i++)
for(int j = 0; j < l1; j++)
{
if(s2[i] == s1[j]) a[i + 1][j + 1] = MIN(a[i][j], MIN(a[i][j + 1] + 1, a[i + 1][j]) + 1);
else a[i + 1][j + 1] = MIN(a[i][j], MIN(a[i][j + 1], a[i + 1][j])) + 1;
}
printf("%d\n", a[l2][l1]);
}
return 0;
}