經(jīng)典DP，給定兩個(gè)字符串x和y，求少的修改次數(shù)將x變成y。修改的規(guī)則只能是如下三種之一：
刪除、插入、改變。同理，用a[i][j]表示把x的前i個(gè)字符變成y的前j個(gè)字符所需的最少操作次數(shù)，則狀態(tài)轉(zhuǎn)移方程為：
當(dāng)x[i]==y[j]時(shí)：a[i][j] = min(a[i-1][j-1],a[i-1][j]+1,a[i][j-1]+1);
當(dāng)x[i]!=y[j]時(shí)：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;
}