源串修改为目标串共操作的次数
给定一个源串和目标串，能够对源串进行如下操作：
1).在给定位置上插入一个字符
2).替换任意字符
3).删除任意字符
写一个程序，返回最小操作次数，使得对源串进行这些操作后等于目标串。

例如：源串”hello”，目标串”lleo”，则通过3次修改可以使得源串变成目标串（删除’h'，删除’e'，在’o'之前插入字符’e'）

分析：这和编程之美中求两串的最长子序列很类似，我们同样采用动态规划的方法求解。首先需要确定的是该题的最优子结构，然后用普通的循环，或递归，或备忘录的方式来实现。设f[i][j]表示源串strA[1..i]变成目标串strB[1..j]所需改动的最小次数,当i=0时表示源串没有字符那么f[0][j]=j;当j=0时，表示目标串没有字符，所以f[i][0]=i;（在动态规划算法中这个初始化，或者叫边界条件很重要！）；如果strA[i]==strB[j]那么f[i][j]=f[i-1][j-1];如果不等那么可以有三种办法

1.插入一个相同的字符，对应的f[i][j]=f[i][j-1]+1；

2.删除那个不同的字符，对应的f[i][j]=f[i-1][j]+1；

3.替换一个相同的字符，对应的f[i][j]=f[i-1][j-1]+1；

这样原理弄清楚了，开始写代码了：

代码如下：

//  [7/7/2013 qingezha] 动态规划 最长公共子序列 c[i][j]表示Xi=｛x1，x2，x3。。。xi｝与Yj=｛y1，y2，。。。yj｝的最长公共字串序列的长度int lcs_length(char x[],char y[],int b[LA+1][LB+1],int c[LA+1][LB+1]){ for (int i=1;i<=LA;++i)  c[i][0]=0; //数组需要初始化，否则值不一定for (int i=1;i<=LB;++i)  c[0][i]=0;for (int i=1;i<=LA;++i){for (int j=1;j<=LB;++j){if (x[i]==y[j])      //序列从1开始计数{c[i][j]=c[i-1][j-1]+1;//把c[i][j] 写成了c[i][i]了，重大失误，造成4个小时的浪费b[i][j]=1;//b记录c的值由哪一个子问题的解得到的} else if(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}else{c[i][j]=c[i][j-1];b[i][j]=3;}}}////////测试代码//////////////////////////////////////////////////////////////////for (int i=1;i<=LA;++i)           //可以将数据输出来看看，哪里有不符合逻辑的错误{for (int j=1;j<=LB;++j){cout<<b[i][j];}cout<<endl;}cout<<endl;for (int i=1;i<=LA;++i){for (int j=1;j<=LB;++j){cout<<c[i][j];}cout<<endl;}cout<<endl; char x[7+2]=" abcdefx";char y[7+2]=" aecxdfx";int b[8][8]={{0}};int c[8][8]={{0}};int a[8]={0};cout<<lcs_length(x,y,b,c)<<endl;lcs(7,7,x,b);//////////////////////////////////////////////////////////////////////////return c[LA][LB];}void lcs(int i,int j,char x[],int b[LA+1][LB+1])//输出最长的公共字串{if(0==i||0==j) return;if (b[i][j]==1){lcs(i-1,j-1,x,b);cout<<x[i]<<" ";}else if(2==b[i][j])lcs(i-1,j,x,b);else lcs(i,j-1,x,b);}