动规求解 最长公共子序列.docx

最长公共子序列 1. 递归方程: C [i][j]= 2. 递归实现 char x[100]; char y[100]; int GetMaxLength(int i ,int j) { if( i ==0|| j ==0) return 0; if( x[i -1]== y[j -1]) return GetMaxLength( i -1, j -1)+1; else {r eturn max( GetMaxLength( i -1, j), GetMaxLength( i, j-1 ) ); }}3. 举例证明子问题假设 x=“ asdfefsw ”,y= “ awfcdfefew ”调用 GetMaxLength (8, 10), 由于 x[8]=y[10] , 调用 GetMaxLength ( 7,9 ),由于 x[7]y[9], 所以调用 GetMaxLength ( 6,9 )和 GetMaxLength ( 7,8 ), 在调用 GetMaxLength ( 6,9 )时, x[6]y[9] , 所以调用 GetMaxLength ( 5,9 )和 GetMaxLength ( 6,8 )。在调用 GetMaxLength ( 7,8 )时, x[7]y[8] , 所以需要调用 GetMaxLength ( 6,8 ) 和 GetMaxLength ( 7,7 )。此时就可以发现我们遇到了第一个重复子问题, 由绿色背景突出显示的即为重复子问题, 两条不同的路都调用了 GetMaxLength ( 6,8 ), 在接下来的更多的问题分析中, 会发现更多的重复子问题,不一一举例。最长公共子序列如下图所示此流程图即为在查找最长公共子序列时所需要的流程: GetMaxLength ( 8,10 ) GetMaxLength ( 7,9 ) GetMaxLength ( 6,9 ) GetMaxLength ( 5,9 ) ...... GetMaxLength ( 6,8 ) ...... GetMaxLength ( 7,8 ) GetMaxLength ( 6,8 ) ...... GetMaxLength ( 7,7 ) ...... 4. 备忘录的实现 int a[100][100]={0}; char x[100]; char y[100]; int GetMaxLength(int i ,int j) { if(a[i][j]!=0) return a[i][j] ; else { if( i ==0|| j ==0) { a[i][j]=0; return a[i][j] ;} if( x[i -1]== y[j -1]) { a[i][j]= GetMaxLength( i -1, j -1)+1; return a[i][j]; } 最长公共子序列 else { a[i][j]= max( GetMaxLength( i -1, j), GetMaxLength( i, j-1 ) ); r eturn a[i][j]; }}}5. 动态规划方程 int memset[100][100]={0}; char x[100]; char y[100]; void GetLCSLength(int m,int n) { for(i