1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<string.h> 4 #define INF 9999; 5  6 void Optimal_BST(double p[],int n){ 7     int i,j,l,r; 8     int root[n+1][n+1]; 9     double e[n+2][n+2];10     double w[n+2][n+2];11     for(i=1;i<=n+1;i++){12         e[i][i-1]=0;13         w[i][i-1]=0;14     }15     16     for(l=1;l<=n;l++){17         for(i=1;   i<=n-l+1;  i++){  // i,j between 1 and n+1，i是左边界，j是右边界 18             j=i+l-1;19             e[i][j]=INF;20             w[i][j]=w[i][j-1]+p[j];     21             for(r=i;r<=j;r++){22                 double temp=e[i][r-1]+e[r+1][j]+w[i][j];23                 if(temp<e[i][j]){24                     e[i][j]=temp;25                     root[i][j]=r;26                 }27             }28         }29     }30     printf("\n\ne table\n");    31     for(i=1;i<=n;i++){32         for(j=1;j<=n;j++){33             if(i>j)printf("          ");34             else printf("%f  ",e[i][j]);35         }36         printf("\n");37     }38     39     printf("\n\nw table\n");40     for(i=1;i<=n;i++){41         for(j=1;j<=n;j++){42             if(i>j)printf("          ");43             else printf("%f  ",w[i][j]);44         }45         printf("\n");46     }47 48     printf("\n\nroot table\n");49     for(i=1;i<=n;i++){50         for(j=1;j<=n;j++){51             if(i>j)printf("  ");52             else printf("%d ",root[i][j]);53         }54         printf("\n");55     }56 }57 58 int main(){59     int n=5;60     double p[6]={-1,0.25,0.2,0.05,0.2,0.3};61     Optimal_BST(p,n);62     return 0;63 }