obstt.cpp

ooptimal binary search tree algorithm using dynamic approach

 #include<iostream.h>
 #include<conio.h>
 int u,i,k,n,r[4][4],b;
 float p[10],m[4][4],mini[10];
 float min(float a[10])
 {
 float g;
 g=1000;
 for(int l=1;l<u;l++)
 {
 if(a[l]<g)
 {g=a[l];
  b=l;
  }
  }
  return g;
  }
void main()
 {
 clrscr();
 cout<<"enter no of nodes";
 cin>>n;
 cout<<"enter prob";
 for(i =1;i<=n;i++)
 cin>>p[i];

 for(i=1;i<=n;i++)
 {
 m[i][i]=p[i];
 r[i][i]=i;
 }
 int fl=1;
 while(fl!=0)
 {
 for(i=1;i<=n;i++)
 {
 for(int j=i+1;j<=n;j++)
 {
 if((m[i][j-1]!=0)&&(m[i+1][j]!=0))
 {
 u=1;
 for(k=i;k<=j;k++)
 {
 mini[u]=m[i][k-1]+m[k+1][j];
 u++;
 }
 m[i][j]=min(mini);
 r[i][j]=b;
 for(k=i;k<=j;k++)
 m[i][j]+=p[k];
 if(m[1][n]!=0)
 {
 fl=0;
 break;
 }
 }
 }
 }
 }
 int j;
 for(i=1;i<=n;i++)
 {
 for(j=1;j<=n;j++)
 {
 cout<<m[i][j]<<'\t';
 }
 cout<<'\n';
 }
 for(i=1;i<=n;i++)
 {
 for(j=1;j<=n;j++)
 {
 cout<<r[i][j]<<'\t';
 }
 cout<<'\n';
 }
 getch();
 }