How to solve binary search tree in O(n^2) ??

[..]

Can anyone kindly give me any hint??
I can only use DP to solve in O(n^3)

[Shahab]

Hi, sir

Are you sure that there is one with O(n^2) or you're just trying find one ? Becuase I think that I must have heard about it if there's one.

And if you find one which its time complexity is lower than O(n^3), I would be happy to hear about that.

Thank you,
Shahab Tasharrofi

[Miguel Angel]

The O(n^2) algorithm, as i have heard, comes in Donald Knuth by Art of Computer Programming.
Here it's an implementation, maybe itsn't the better, because without recursion it will be faster. Greetings .

[cpp]
#include<iostream.h>

#define INF 2147483647
#define MaxN 10

long m[MaxN+1][MaxN+1];
int w[MaxN+1];
int s[MaxN+1][MaxN+1];
int f[MaxN+1];

long findBest(int l, int r)
{
int i;
long left, right;
if (m[l][r] < 0)
{
m[l][r] = INF;
findBest(l, r-1);
findBest(l+1, r);
for (i=s[l][r-1]; i<=s[l+1][r]; i++)
{
left = 0;
if (i > l)
left = findBest(l, i-1) + w[i-1] - w[l-1];
right = 0;
if (i < r)
right = findBest(i+1, r) + w[r] - w;
if (left + right < m[l][r])
{
m[l][r]= left + right;
s[l][r]= i;
}
}
}
return m[l][r];
}

void main()
{
int i, j, n;
while (cin >> n)
{
w[0] = 0;
for (i=1; i<=n; i++)
{
cin >>f;
w = f + w[i-1];
}
for (i=1; i<=n; i++)
{
m = 0;
s = i;
}
for (i=1; i<n; i++)
for (j=i+1; j<=n; j++)
{
m[j] = -1;
m[j] = -1;
}
cout<<findBest(1, n)<<endl;
}
}
[/cpp]