题目链接：https://vjudge.net/problem/POJ-3356
题意就是给定字符串x和y,可以对x进行如下操作：插入一个字符，删除一个字符，或者将一个字符变成另一个；求将x变成y的最小操作数
设dp[i][j]表示字符串x到第i位，y到第j位的最小操作数；则dp[i-1][j]+1表示当前删除x[i]的最小操作数，dp[i][j-1]+1表示添加y[j]的最小操作数
又有：若x[i]=y[j]，dp[i][j]可以由dp[i-1][j-1]直接转移而来；若x[i]≠y[j]，dp[i][j]可以由dp[i-1][j-1]+1转移而来（将x第i位变成y第j位）
于是有转移方程：
dp[i][j]=min(dp[i-1][j-1]+1,dp[i-1][j]+1,dp[i][j-1]+1)，若x[i]=y[j]
dp[i][j]=min(dp[i-1][j-1],dp[i-1][j]+1,dp[i][j-1]+1),若x[i]≠y[j]
注意初始化：dp[i][0]=i(1<=i<=lenx)，dp[0][j]=j(1<=j<=leny)，dp[0][0]=0
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int maxn=100+10; 6 char x[maxn],y[maxn]; 7 int lenx,leny,i,j,k; 8 int dp[maxn][maxn]; 9 10 int main(){ 11 while (~scanf("%d",&lenx)){ 12 scanf("%s%d%s",x+1,&leny,y+1); //* 13 memset(dp,0,sizeof(dp)); 14 for (i=1;i<=lenx;i++) dp[i][0]=i; 15 for (i=1;i<=leny;i++) dp[0][i]=i; 16 for (i=1;i<=lenx;i++) 17 for (j=1;j<=leny;j++){ 18 if (x[i]==y[j]) dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j]+1,dp[i][j-1]+1)); //* 19 else dp[i][j]=min(dp[i-1][j-1]+1,min(dp[i-1][j]+1,dp[i][j-1]+1)); 20 } 21 printf("%d ",dp[lenx][leny]); 22 } 23 return 0; 24 }