1 /*  2 字符串编辑问题，给定一个源字符串和目的字符串，源字符串可以insert，delete，replace，求最少操作使其变成目标字符串，有两种方法，方法一采用  3 动态规划方法，f[i][j]=min{f[i-1][j]+1,f[i+1][j]+1,f[i-1][j-1]+(s[i]==t[j]?0:1)}.方法二采用递归实现（这个是求相似度，意思是一样的），没有动态规划好  4 两个子串一个到另一的距离和另一个到它的距离是一样的。  5 */  6   7 #include <iostream>  8 using namespace std;  9 #include <string> 10  11 //动态规划方法，f[i][j]表示从【0--i】和【0---j】的最小操作数， 12 /* 13 f[i][j]=min{f[i-1][j]+1(此为删除s[i]操作)，f[i][j-1]+1(此为增加d[j]操作，f[i-1][j-1]+(s[i]==d[j]?0:1)(此为，如果s[i]==d[j]，则说明相等，不用操作，否则替换操作) 14 f[0][0]=0; 15 f[0][j]={0,1,2,3,4,5,6,....j};   //都为插入 16 f[i][0]={0,1,2,3,.....i};         //都为删除 17 */ 18  19 int minoperation(const string & sour,const string & dest) 20 { 21     int row=sour.size(); 22     int colom=dest.size(); 23     if(row==0)               //直接插入或删除 24         return colom; 25     if(colom==0) 26         return row; 27     int ** result=new int * [row+1]; 28     if(result==NULL) 29     { 30         cout<<"wrong"<<endl; 31         exit(1); 32     } 33     for(int i=0;i<=row;i++) 34     { 35         result[i]=new int[colom+1]; 36         if(result[i]==NULL) 37         { 38             cout<<"wrong"<<endl; 39             exit(1); 40         } 41     } 42     for(int i=0;i<=row;i++) 43         result[i][0]=i; 44     for(int j=1;j<=colom;j++) 45         result[0][j]=j; 46     for(int i=1;i<=row;i++) 47         for(int j=1;j<=colom;j++) 48         { 49             result[i][j]=min(min(result[i-1][j]+1,result[i][j-1]+1),result[i-1][j-1]+(sour[i-1]==dest[j-1]?0:1));  //注意sour[i-1]是因为sour是从0开始，而result多了开始的0. 50         } 51     int tmp=result[row][colom]; 52     for(int i=0;i<=row;i++) 53         delete[] result[i]; 54     delete[] result; 55     return tmp; 56 } 57  58 /* 59 方法二，采用递归的方法 60 s="ACAATCC" 61 D="AGCATGC" 62 两个指针分别指向两个序列，sbegin,dbegin. 63 */ 64 int minoperation2(const string & sour,const string & dest,int sbegin,int send,int dbegin,int dend) 65 { 66     if(sbegin>send)                67     { 68         if(dbegin<dend)                //最后没有了，只能全删除或全添加上才能一样 69         { 70             return dend-dbegin+1; 71         } 72         else 73             return 0; 74     } 75     if(dbegin>dend) 76     { 77         if(sbegin<send)           //最后没有了，只能全删除或全添加上才能一样 78         { 79             return send-sbegin+1; 80         } 81         else 82             return 0; 83     } 84     if(sour[sbegin]==dest[dbegin]) 85     { 86         return minoperation2(sour,dest,sbegin+1,send,dbegin+1,dend); 87     } 88     else 89     { 90         int t1=minoperation2(sour,dest,sbegin+1,send,dbegin+1,dend); 91         int t2=minoperation2(sour,dest,sbegin,send,dbegin+1,dend); 92         int t3=minoperation2(sour,dest,sbegin+1,send,dbegin,dend); 93         return min(min(t1,t2),t3)+1; 94     } 95 } 96 int main() 97 { 98     string source="ACAATCC"; 99     string dest="AGCATGC";100     //cout<<minoperation(source,dest)<<endl;101     cout<<minoperation2(source,dest,0,source.size(),0,dest.size())<<endl;102     system("pause");103 }