最优二叉搜索树动态规划c语言实现

最优二叉搜索树（Optimal Binary Search Tree）是一种特殊的二叉搜索树，它的查找效率最高。动态规划是解决最优二叉搜索树问题的常用方法。下面是一个用C语言实现最优二叉搜索树的动态规划算法的示例：

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

// 定义最大关键字数量
#define MAX_KEYS 10

// 动态规划函数
void optimalBST(int keys[], float freq[], int n)
{
    // 创建两个二维数组来存储子问题的解
    float cost[n + 1][n + 1];
    float sum[n + 1][n + 1];

    // 初始化对角线上的值
    for (int i = 0; i <= n; i++)
    {
        cost[i][i] = freq[i];
        sum[i][i] = freq[i];
    }

    // 计算其他位置的值
    for (int L = 2; L <= n; L++)
    {
        for (int i = 0; i <= n - L + 1; i++)
        {
            int j = i + L - 1;
            cost[i][j] = INT_MAX;
            sum[i][j] = sum[i][j - 1] + freq[j];

            for (int r = i; r <= j; r++)
            {
                float c = ((r > i) ? cost[i][r - 1] : 0) +
                          ((r < j) ? cost[r + 1][j] : 0) +
                          sum[i][j];
                if (c < cost[i][j])
                    cost[i][j] = c;
            }
        }
    }

    printf("最小搜索代价为：%f\n", cost[n - 1]);
}

int main()
{
    int keys[MAX_KEYS] = {1, 2, 3, 4, 5};
    float freq[MAX_KEYS] = {0.2, 0.1, 0.15, 0.3, 0.25};
    int n = sizeof(keys) / sizeof(keys);

    optimalBST(keys, freq, n);

    return 0;
}

这段代码实现了最优二叉搜索树的动态规划算法。它首先创建了两个二维数组来存储子问题的解，然后通过两层循环计算出每个子问题的最优解。最后输出最小搜索代价。