Advertisement

动态规划中,在给定两个字符串a和b的情况下,在允许进行删除、插入或替换操作的基础上求解将一个字符串转换为另一个字符串所需的最小操作次数

阅读量:

咱这里直接把代码贴出来,造福各位同学

解析在后面

复制代码
    #include <iostream>
    #include <string>
    using namespace std;
    
    const int Max = 1000;
    char a[Max],b[Max];
    int f[Max][Max];
    int m , n;
    
    int main (void) {
    	int n , m ;
    	cin>>n>>m>>a+1>>b+1;
    	for (int i = 0; i <=m; i++) {//colmn 0 and row 0 means the NULL transforms into the target string.
    		f[i][0]=i;
    	}
    	for (int j = 0; j <=n; j++) {
    		f[0][j]=j;
    	} 
    	
    	/*the equation: f(x,y)= {
    		colmn 0 and row 0 = i or j , 					i=0 or j = 0;
    		min( f(i-1,j)+1, f(i,j-1)+1, f(i-1,j-1)+

全部评论 (0)

还没有任何评论哟~