问题简述：
输入两个序列x和y，分别执行下列三个步骤，将序列x转化为y
（1）插入；（2）删除；（3）替换；
要求输出最小操作数。
原题链接：http://poj.org/problem?id=3356
解题思路：
明显的动态规划题，输入两个字符串 a[0...m-1] , b[0...n]
使用二维数组 dp[i,j] 记录 a[0...i] 和 b[0...j] 对应的最小操作数
显然有以下递归方程：
dp[i,0] = i
dp[0,j] = j
dp[i,j] = dp[i-1,j-1] if a[i-1]==b[j-1]
dp[i,j] = min(dp[i-1,j-1],dp[i-1,j],dp[i,j-1]) + 1 if a[i-1]!=b[j-1]
源代码
/*
OJ: POJ
ID: 3013216109
TASK: 3356.AGTC
LANG: C++
NOTE: DP
*/
#include <cstdio> const int MAX=;
int m,n,i,j,k;
char a[MAX],b[MAX];
int dp[MAX][MAX],c[MAX]; int min(int x,int y,int z) {
if(x<+y&&x<=z)
return x;
if(y<=x&&y<=z)
return y;
if(z<=x&&z<=y)
return z;
} int main()
{
while(scanf("%d %s",&m,a)!=EOF) {
scanf("%d %s",&n,b);
for(i=;i<=m;i++)
dp[i][]=i;
for(j=;j<=n;j++)
dp[][j]=j;
k=;
for(i=;i<=m;i++) {
for(j=;j<=n;j++) {
if(a[i-]==b[j-])
dp[i][j]=dp[i-][j-];
else
dp[i][j]=min(dp[i-][j-],dp[i-][j],dp[i][j-])+;
}
}
printf("%d\n",dp[m][n]);
}
return ;
}