C语言，通过递推式实现最优二叉搜索树并给出代码

好的，您的问题是如何用递推式实现最优二叉搜索树，以下是示例代码：

#include <stdio.h>
#include <stdlib.h>

#define INF 2147483647

//计算从i到j的W值之和
int sum_W(int *W, int i, int j)
{
    int k, sum = 0;
    for (k = i; k <= j; k++)
        sum += W[k];
    return sum;
}

//计算最优二叉搜索树的平均代价
float optimal_bst(int n, float *p, int *W, float *C)
{
    int i, j, r, len;
    float tmp;
    for (i = 0; i <= n; i++) {
        C[i * (n+1) + i] = p[i];
        W[i * (n+1) + i] = p[i];
    }
    //计算C(i,j)和W(i,j)
    for (len = 2; len <= n; len++) {
        for (i = 0; i <= n-len+1; i++) {
            j = i + len - 1;
            W[i * (n+1) + j] = W[i * (n+1) + j-1] + p[j] + sum_W(p, i, j-1);
            C[i * (n+1) + j] = INF;
            for (r = i; r <= j; r++) {
                tmp = C[i * (n+1) + r-1] + C[(r+1) * (n+1) + j] + W[i * (n+1) + j];
                if (tmp < C[i * (n+1) + j])
                    C[i * (n+1) + j] = tmp;
            }
        }
    }
    return C[0 * (n+1) + n];
}

int main()
{
    int n = 4;
    float p[] = {0.15, 0.10, 0.05, 0.10, 0.20};
    int *W = (int *)malloc(sizeof(int) * (n+1) * (n+1));
    float *C = (float *)malloc(sizeof(float) * (n+1) * (n+1));

    float optimal_cost = optimal_bst(n, p, W, C);

    printf("The optimal cost of the BST is: %.2f\n", optimal_cost);

    free(W);
    free(C);
    return 0;
}

这是一个动态规划算法，利用递推式计算最优二叉搜索树的平均代价。其中，W(i,j)表示由i到j的节点组成的二叉搜索树的查找代价之和，C(i,j)表示由i到j的节点组成的最优二叉搜索树的平均查找代价。在计算C(i,j)时，枚举根节点r，将树分成左右两个子树，选择代价最小的作为最优解。