C++最优二叉搜索树详细代码

最优二叉搜索树（Optimal Binary Search Tree）是一种动态规划的算法，用于在给定一组键和它们的概率时构建最优的二叉搜索树。

下面是 C 语言实现最优二叉搜索树的详细代码：

#include <stdio.h>
#include <limits.h>

#define MAX_KEYS 100

int keys[MAX_KEYS];
int freq[MAX_KEYS];
int n;

int sum(int freq[], int i, int j) {
    int s = 0;
    for (int k = i; k <= j; k++) {
        s += freq[k];
    }
    return s;
}

int opt_cost(int freq[], int i, int j) {
    if (j < i) {
        return 0;
    }
    if (j == i) {
        return freq[i];
    }

    int fsum = sum(freq, i, j);
    int min_cost = INT_MAX;

    for (int r = i; r <= j; r++) {
        int cost = opt_cost(freq, i, r-1) +
                   opt_cost(freq, r+1, j) +
                   fsum;
        if (cost < min_cost) {
            min_cost = cost;
        }
    }

    return min_cost;
}

int main() {
    printf("Enter the number of keys: ");
    scanf("%d", &n);

    printf("Enter the keys:\n");
    for (int i = 0; i < n; i++) {
        scanf("%d", &keys[i]);
    }

    printf("Enter the frequencies:\n");
    for (int i = 0; i < n; i++) {
        scanf("%d", &freq[i]);
    }

    int cost = opt_cost(freq, 0, n-1);

    printf("Minimum cost of optimal BST is %d.\n", cost);

    return 0;
}

代码中，`sum()` 函数用于计算频率数组 `freq[]` 中下标从 `i` 到 `j` 的元素之和，`opt_cost()` 函数则是实现最优二叉搜索树的核心算法。`opt_cost()` 函数使用递归的方法，枚举所有可能的根节点，计算出每个根节点对应的最小成本，并返回其中的最小值。

在主函数中，输入了键和频率数组，并调用 `opt_cost()` 函数计算出最小成本。

需要注意的是，该代码仅仅是计算了最小成本，并没有构建出最优二叉搜索树的结构。如果需要构建出最优二叉搜索树，需要在递归过程中记录每个子树的根节点，然后根据这些根节点的位置来构建树的结构。