jisuanzuiyouji.txt

计算最优积

c) 计算最优值 
由于在所考虑的子问题空间中，总共只有θ(m*n)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。 
计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>作为输入。输出两个数组c[0..m ,0..n]和b[1..m ,1..n]。其中c[i,j]存储Xi与Yj的最长公共子序列的长度，b[i,j]记录指示c[i,j]的值是由哪一个子问题的解达到的，这在构造最长公共子序列时要用到。最后，X和Y的最长公共子序列的长度记录于c[m,n]中。 
程序如下： 
#include<stdio.h> 
#include<string.h> 
int lcs_length(char x[], char y[]); 
int main() 
{ 
char x[100],y[100]; 
int len; 
while(1) 
{ 
scanf("%s%s",x,y); 
if(x[0]=='0') //约定第一个字符串以‘0’开始表示结束 
break; 
len=lcs_length(x,y); 
printf("%d\n",len); 
} 
} 
int lcs_length(char x[], char y[] ) 
{ 
int m,n,i,j,l[100][100]; 
m=strlen(x); 
n=strlen(y); 
for(i=0;i<m+1;i++) 
l[i][0]=0; 
for(j=0;j<n+1;j++) 
l[0][j]=0; 
for(i=1;i<=m;i++) 
for(j=1;j<=n;j++) 
if(x[i-1]==y[j-1]) //i,j从1开始，但字符串是从0开始 
l[i][j]=l[i-1][j-1]+1; 
else if(l[i][j-1]>l[i-1][j]) 
l[i][j]=l[i][j-1]; 
else 
l[i][j]=l[i-1][j]; 
return l[m][n]; 
} 
由于每个数组单元的计算耗费Ο(1)时间，算法lcs_length耗时Ο(mn)。