利用动态规划法C++最优二叉检索树问题：求结点S[1,5] = {A,B,C,D,E}，概率分别为P = {0.04,0.1,0.02,0.3,0.02,0.1,0.05,0.2, 0.06,0.1,0.01}的最优二叉检索树。

首先，需要将节点按照概率从小到大排序，得到S[1,5] = {C,E,A,B,D}，概率分别为{0.02,0.02,0.04,0.1,0.3}。

接着，定义一个二维数组dp[1,5][1,5]，其中dp[i][j]表示从第i个节点到第j个节点所构成的最优二叉检索树的期望代价。同时，定义一个二维数组root[1,5][1,5]，其中root[i][j]表示从第i个节点到第j个节点所构成的最优二叉检索树的根节点编号。

接下来，需要根据动态规划的思想，逐步求解dp数组和root数组。

当i=j时，即只有一个节点时，dp[i][j]=q[i]，root[i][j]=i。

当i<j时，假设k为节点i到j中的根节点，则有如下递推式：

dp[i][j] = min(dp[i][k-1] + dp[k+1][j] + sum(q[i...j]))
root[i][j] = k

其中，sum(q[i...j])表示节点i到j的概率之和。

最终，dp[1][5]即为所求的最优二叉检索树的期望代价，root[1][5]即为根节点的编号。

下面是具体的代码实现：

相关问题

利用动态规划法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;
}

C++编程完成动态规划法求解最优二叉搜索树，随机化查找数字及其查找成功概率，求出最优二叉搜索树。

以下是C++代码实现：

#include <iostream>
#include <vector>
#include <climits>
#include <ctime>
#include <cstdlib>

using namespace std;

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

void optimal_bst(vector<double> p, int n) {
    vector<vector<double>> e(n + 1, vector<double>(n + 1, 0));
    vector<vector<double>> w(n + 1, vector<double>(n + 1, 0));
    vector<vector<int>> root(n + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= n; i++) {
        e[i][i - 1] = 0;
        w[i][i - 1] = 0;
    }
    for (int len = 1; len <= n; len++) {
        for (int i = 1; i <= n - len + 1; i++) {
            int j = i + len - 1;
            e[i][j] = INT_MAX;
            w[i][j] = w[i][j - 1] + p[j];
            for (int r = i; r <= j; r++) {
                double t = e[i][r - 1] + e[r + 1][j] + w[i][j];
                if (t < e[i][j]) {
                    e[i][j] = t;
                    root[i][j] = r;
                }
            }
        }
    }
    cout << "最小代价为：" << e[1][n] << endl;
    cout << "构造的最优二叉搜索树为：" << endl;
    cout << "根节点为" << root[1][n] << endl;
    vector<int> q;
    q.push_back(root[1][n]);
    vector<int> left(1, 1), right(1, n);
    while (!q.empty()) {
        int r = q.back();
        q.pop_back();
        int i = left.back();
        left.pop_back();
        int j = right.back();
        right.pop_back();
        if (r - 1 >= i && root[i][r - 1] != 0) {
            cout << "根节点为" << root[i][r - 1] << "的左子树为" << i << "到" << r - 1 << endl;
            left.push_back(i);
            right.push_back(r - 1);
            q.push_back(root[i][r - 1]);
        }
        if (r + 1 <= j && root[r + 1][j] != 0) {
            cout << "根节点为" << root[r + 1][j] << "的右子树为" << r + 1 << "到" << j << endl;
            left.push_back(r + 1);
            right.push_back(j);
            q.push_back(root[r + 1][j]);
        }
    }
}

int main() {
    srand(time(nullptr));
    vector<double> p{0, 0.15, 0.10, 0.05, 0.10, 0.20};
    optimal_bst(p, 5);
    cout << "随机化查找数字及其查找成功概率：" << endl;
    double s = sum(p, 1, 5);
    for (int i = 1; i <= 5; i++) {
        double r = (double) rand() / RAND_MAX;
        double sum = 0;
        for (int j = 1; j <= 5; j++) {
            sum += p[j];
            if (r < sum / s) {
                cout << "随机数为" << r << "，查找数字为" << j << "，查找成功概率为" << p[j] / s << endl;
                break;
            }
        }
    }
    return 0;
}

其中，`optimal_bst`函数实现动态规划求解最优二叉搜索树，`sum`函数用于计算概率之和，`main`函数中实现随机化查找数字及其查找成功概率。在本例中，我们以一组数据{0.15,0.10,0.05,0.10,0.20}为例进行了求解。