首页 > 试题广场 >

最优二叉搜索树问题的动态规划算法(设函数名 binary

[问答题]

最优二叉搜索树问题的动态规划算法(设函数名 binarysearchtree)

void binarysearchtree(int a[],int b[],int n,int **m,int **s,int **w)

{

int i,j,k,t,l;

for(i=1;i<=n+1;i++)

{

w[i][i-1]=a[i-1];

m[i][i-1]=0;

}

for(l=0;l<=n-1;l++)//----l 是下标 j-i 的差

for(i=1;i<=n-l;i++)

{

j=i+l;

w[i][j]=w[i][j-1]+a[j]+b[j];

m[i][j]=m[i][i-1]+m[i+1][j]+w[i][j];

s[i][j]=i;

for(k=i+1;k<=j;k++)

{

t=m[i][k-1]+m[k+1][j]+w[i][j];

if(t<m[i][j])

{

m[i][j]=t;

s[i][j]=k;

}

}

}

}

发表于 2017-07-31 15:29:01 回复(0)