最优二分搜索树动态规划

设S=(x1,x2,…,xn)是有序集，且x1<x2<…<xn，已知键值和区间的存取概率分布为(a0,b1,a1,b2,…,bn,an)，其中ai表示相应区间的搜索概率，bi表示相应键值的搜索概率。在所有表示有序集的二叉树中找出一棵具有最小平均路长的二叉搜索树

#include

float w[100][100] min[100][100];
int head[100][100] n;

void optimalBinarySearchTree （float a[] float b[]）
{
    for （int i = 0; i <= n; i++）
    {
        w[i + 1][i] = a[i];
        min[i + 1][i] = 0;
        head[i + 1][i] = 0;
    }
    for （int r = 0; r < n; r++）
        for （int i = 1; i <= n - r; i++）
        {
            int j = i + r
                ihead = head[i][j - 1] > i ? head[i][j - 1] : i
                jhead = head[i + 1][j] > i ? head[i + 1][j] : j;
            w[i][j] = w[i][j - 1] + a[j] + b[j];
            min[i][j] = min[i][ihead - 1] + min[ihead + 1][j];
            head[i][j] = ihead;

            for （int k = ihead + 1; k <= jhead; k++）
            {
                float temp = min[i][k - 1] + min[k + 1][j];
                if （temp <= min[i][j]）
                {
                    min[i][j] = temp;
                    head[i][j] = k;
                }
            }
            min[i][j] += w[i][j];
        }
}

void in_traversal （int left int right）