```
// program to solve optimal binary search tree problem with dynamic programming
#include<iostream.h>
#include<conio.h>
struct node
{
int data;
struct node *left,*right;
};
typedef struct node node;
class binary
{
private:
int w[10][10],c[10][10],r[10][10],n;
int p[10],q[11];
int find(int,int);
node *cnst_tree(int,int);
public:
void obst();
void setdata();
node *tree();
};
node *binary::tree()
{
return(cnst_tree(0,n));
}
void binary :: setdata()
{
int i,j;
cout<<"\nEnter number of identifiers: ";
cin>>n;
cout<<"\nEnter values for P vector ("<<n<<" values): ";
for(i=1;i<=n;i++)
cin>>p[i];
cout<<"\nEnter values for Q vector ("<<n+1<<" values): ";
for(i=0;i<=n;i++)
cin>>q[i];
}
void binary :: obst()
{
int i,j,k,m;
for(i=0;i<=n-1;i++)
{
w[i][i]=q[i];
r[i][i]=0;
c[i][i]=0;
w[i][i+1]=p[i+1]+q[i+1]+q[i];
r[i][i+1]=i+1;
c[i][i+1]=w[i][i+1];
}
w[n][n]=q[n];
r[n][n]=0;
c[n][n]=0;
for(m=2;m<=n;m++)
for(i=0;i<=n-m;i++)
{
j=i+m;
w[i][j]=w[i][j-1]+p[j]+q[j];
k=find(i,j);
c[i][j]=w[i][j]+c[i][k-1]+c[k][j];
r[i][j]=k;
}
}
int binary ::find(int i,int j)
{
int min=32767,m,l;
m=r[i][j-1];
while(m<=r[i+1][j])
{
if(c[i][m-1]+c[m][j]<min)
{
min=c[i][m-1]+c[m][j];
l=m;
}
m++;
}
return l;
}
node * binary::cnst_tree(int i,int j)
{
int k;
node *p= new node;
k=r[i][j];
if(k==0)
return NULL;
else
{
p->data=k;
p->left=cnst_tree(i,k-1);
p->right=cnst_tree(k,j);
return p;
}
}
void inorder (node *x)
{
if(x)
{
inorder(x->left);
cout<<x->data<<"\t";
inorder(x->right);
}
}
void main()
{
node *root;
binary b;
clrscr();
b.setdata();
b.obst();
root=b.tree();
cout<<"\nTree in inorder traversal is: \n\n\t";
inorder(root);
getch();
}
```