利用动态规划法C++最优二叉检索树

最优二叉搜索树是一种特殊的二叉搜索树，其中查找每个关键字的期望代价最小。这里我们使用动态规划算法来解决这个问题。

假设我们有关键字 $k_1, k_2, \cdots, k_n$，它们被存储在一个有序数组中，且对于每个关键字 $k_i$，它的概率为 $p_i$。我们也有一些虚拟关键字 $d_0, d_1, \cdots, d_n$，其中 $d_0$ 代表小于 $k_1$ 的所有值，$d_n$ 代表大于 $k_n$ 的所有值。我们定义 $w_{i,j}$ 表示 $k_i, k_{i+1}, \cdots, k_j$ 以及 $d_{i-1}, d_i, \cdots, d_j$ 的概率和。我们还定义 $c_{i,j}$ 表示最优二叉搜索树中 $k_i, k_{i+1}, \cdots, k_j$ 的期望代价。

为了找到最优二叉搜索树，我们可以使用以下递推式：

$$
c_{i,j} = \begin{cases}
0, & \text{if } i=j+1 \\
\min\limits_{i\leq k\leq j} \{c_{i,k-1} + c_{k+1,j}\} + w_{i,j}, & \text{if } i\leq j
\end{cases}
$$

递推式的含义是，我们将可能的根节点 $k$ 从 $i$ 到 $j$ 进行枚举，对于每个 $k$，计算左子树 $i$ 到 $k-1$ 的期望代价 $c_{i,k-1}$ 和右子树 $k+1$ 到 $j$ 的期望代价 $c_{k+1,j}$，然后加上 $k$ 作为根节点的期望代价 $w_{i,j}$。最后取所有可能的 $k$ 中，期望代价最小的那个值作为 $c_{i,j}$ 的值。

最终，我们可以通过计算 $c_{1,n}$ 来获得最优二叉搜索树的期望代价。

下面是一个使用动态规划算法计算最优二叉搜索树的示例程序，其中输入的关键字概率存储在数组 $p$ 中，虚拟关键字的概率为 $q$。程序输出最优二叉搜索树的期望代价。

#include <stdio.h>

double opt_bst(int n, double p[], double q[]) {
    double w[n+1][n+1];
    double c[n+1][n+1];

    for (int i = 0; i <= n; i++) {
        w[i][i] = q[i];
        c[i][i] = 0;
    }

    for (int len = 1; len <= n; len++) {
        for (int i = 0; i <= n-len; i++) {
            int j = i + len;
            w[i][j] = w[i][j-1] + p[j] + q[j];
            c[i][j] = __DBL_MAX__;
            for (int k = i; k <= j; k++) {
                double cost = c[i][k-1] + c[k+1][j] + w[i][j];
                if (cost < c[i][j]) {
                    c[i][j] = cost;
                }
            }
        }
    }

    return c[0][n];
}

int main() {
    double p[] = {0.15, 0.10, 0.05, 0.10, 0.20};
    double q[] = {0.05, 0.10, 0.05, 0.05, 0.05, 0.10};
    int n = sizeof(p) / sizeof(p[0]);

    double cost = opt_bst(n-1, p, q);
    printf("The expected cost of the optimal binary search tree is %f\n", cost);

    return 0;
}