信息检索的基本方法：构造检索式

下面是 C++ 实现构造最优二分检索树的示例代码，其中假设有 n 个关键字和 n+1 个虚拟关键字： ```c++ #include <iostream> using namespace std; const int MAXN = 100; int w[MAXN]; // 关键字权值 int v[MAXN + 1][MAXN + 1]; // 子问题的最优解 int root[MAXN + 1][MAXN + 1]; // 子问题的最优解对应的根节点 // 构造最优二分检索树 void optimal_bst(int n) { // 初始化子问题的最优解 for (int i = 1; i <= n + 1; i++) { v[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; v[i][j] = INT_MAX; // 枚举根节点 for (int k = i; k <= j; k++) { int cost = v[i][k - 1] + v[k + 1][j] + w[k]; if (cost < v[i][j]) { v[i][j] = cost; root[i][j] = k; } } } } } int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> w[i]; } optimal_bst(n); cout << "最小代价为：" << v[1][n] << endl; return 0; } ``` 在上述代码中，数组 `v` 存储子问题的最优解，数组 `root` 存储子问题的最优解对应的根节点。函数 `optimal_bst` 利用动态规划的思想，从子问题规模为 1 的情况开始，逐步扩大子问题规模，直到求解整个问题。最终，函数输出最优解 `v[1][n]`。