最优二叉搜索树代码c++

以下是C++的最优二叉搜索树代码：

#include <iostream>
#include <vector>
using namespace std;

// 动态规划算法求解最优二叉搜索树
float optimalBST(vector<float>& p, vector<float>& q, int n) {
    // e[i][j]表示节点[i, j]为根节点的最小期望代价
    // w[i][j]表示节点[i, j]的概率和
    vector<vector<float>> e(n + 2, vector<float>(n + 1, 0));
    vector<vector<float>> w(n + 2, vector<float>(n + 1, 0));
    for (int i = 1; i <= n + 1; i++) {
        e[i][i - 1] = q[i - 1];
        w[i][i - 1] = q[i - 1];
    }
    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] + q[j];
            for (int k = i; k <= j; k++) {
                float cost = e[i][k - 1] + e[k + 1][j] + w[i][j];
                if (cost < e[i][j]) {
                    e[i][j] = cost;
                }
            }
        }
    }
    return e[1][n];
}

int main() {
    vector<float> p = {0.00, 0.15, 0.10, 0.05, 0.10, 0.20};
    vector<float> q = {0.05, 0.10, 0.05, 0.05, 0.05, 0.10};
    int n = p.size() - 1;
    cout << "最小期望代价为：" << optimalBST(p, q, n) << endl;
    return 0;
}

其中，p为节点的概率，q为虚拟节点的概率，n为节点个数。