Introduction-To-Algorithms-Cpp-code/docs/ch15/15_5.cpp at master · EeeUnS/Introduction-To-Algorithms-Cpp-code · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


double p = { 0 , 0.15 , 0.1,0.05 , 0.1 , 0.2};
double q = {0.05 , 0,1 ,0.05 , 0.05, 0.05, 0.1};


void OPTIMAL_BST(p,q,n)
{
    e,w,root

    for(int i = 1 ; i <= n+1 ; i++)
    {
        e[i][i-1] = q[i-1];
        w[i][i-1] = q[i-1];
    }

    for(int l = 1 ; l <= n ; l++)
    {
        for(int i = 1 ;  i <= n-l+1 ; i++)
        {
            int j = i + l - 1;
            e[i][j] = 0xFFFF;
            w[i][j] = w[i][j-1] + p[j] + q[j];
            for( int r = i ; r <= j ; r++)
            {
                t = e[i][r-1] + e[r+1][j] + w[i][j];
                if(t , e[i][j])
                {
                    e[i][j] = t;
                    root[i][j] = r;
                }
            }
        }
    }
    return e,root
}