最优二叉搜索树,C++,代码,注释,vector

以下是最优二叉搜索树的C++代码，附有注释和使用vector实现：

#include <iostream>
#include <vector>
#include <limits.h> //包含INT_MAX
using namespace std;

//计算最优二叉搜索树
void optimal_bst(vector<int> keys, vector<int> freq) {
    int n = keys.size(); //关键字数量
    vector<vector<int>> cost(n+1, vector<int>(n+1)); //存放最小代价
    vector<vector<int>> root(n, vector<int>(n)); //存放最小代价的根节点
    for (int i = 0; i < n; i++) {
        cost[i][i] = freq[i]; //初始化对角线上的值
        root[i][i] = i; //初始化对角线上的根节点
    }
    for (int len = 2; len <= n; len++) { //计算长度为2到n的子树
        for (int i = 0; i <= n-len; i++) {
            int j = i + len - 1; //子树的右端点
            cost[i][j] = INT_MAX; //初始化最小代价为最大值
            for (int k = i; k <= j; k++) {
                int left_cost = (k > i) ? cost[i][k-1] : 0;
                int right_cost = (k < j) ? cost[k+1][j] : 0;
                int sum_freq = 0; //计算i到j关键字的总频率
                for (int m = i; m <= j; m++) {
                    sum_freq += freq[m];
                }
                int total_cost = left_cost + right_cost + sum_freq; //当前代价
                if (total_cost < cost[i][j]) { //更新最小代价和根节点
                    cost[i][j] = total_cost;
                    root[i][j] = k;
                }
            }
        }
    }
    cout << "最小代价为：" << cost[0][n-1] << endl;
}

int main() {
    vector<int> keys = {10, 12, 16, 21}; //关键字
    vector<int> freq = {4, 2, 6, 3}; //频率
    optimal_bst(keys, freq);
    return 0;
}

注释详解：

1. `optimal_bst`函数用于计算最优二叉搜索树。参数包括关键字`keys`和频率`freq`，分别存放关键字和对应的频率。

2. `cost`和`root`分别是两个二维向量，用于存放最小代价和对应的根节点。

3. 初始化`cost`和`root`的对角线。

4. 计算长度为2到n的子树，从左到右，从上到下依次计算每个子树的最小代价。

5. `k`遍历`i`到`j`之间的关键字，计算左子树和右子树的最小代价，以及当前子树的总频率。

6. 如果当前代价小于最小代价，则更新最小代价和对应的根节点。

7. `main`函数中定义了测试数据，调用`optimal_bst`函数并输出结果。