最优二叉搜索树动态规划c
时间: 2023-07-23 17:26:47 浏览: 54
下面是最优二叉搜索树的动态规划算法的C++实现:
```c++
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1005;
const int INF = 0x3f3f3f3f;
int n;
int w[N], sw[N]; // w[i] 表示第 i 个节点的权值,sw[i] 表示前 i 个节点的权值之和
int f[N][N], root[N][N]; // f[i][j] 表示从第 i 个节点到第 j 个节点构成的最优二叉搜索树的代价,root[i][j] 表示从第 i 个节点到第 j 个节点构成的最优二叉搜索树的根节点编号
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> w[i];
sw[i] = sw[i-1] + w[i];
}
memset(f, INF, sizeof f);
for (int i = 1; i <= n; i++)
f[i][i] = w[i], root[i][i] = i;
for (int len = 2; len <= n; len++) { // 枚举区间长度
for (int i = 1; i + len - 1 <= n; i++) { // 枚举区间左端点
int j = i + len - 1; // 区间右端点
for (int k = root[i][j-1]; k <= root[i+1][j]; k++) { // 枚举根节点
int cost = (k == i ? 0 : f[i][k-1]) + (k == j ? 0 : f[k+1][j]) + sw[j] - sw[i-1] - w[k];
if (cost < f[i][j]) {
f[i][j] = cost;
root[i][j] = k;
}
}
}
}
cout << f[1][n] << endl;
return 0;
}
```
其中 `w[i]` 表示第 `i` 个节点的权值,`sw[i]` 表示前 `i` 个节点的权值之和,`f[i][j]` 表示从第 `i` 个节点到第 `j` 个节点构成的最优二叉搜索树的代价,`root[i][j]` 表示从第 `i` 个节点到第 `j` 个节点构成的最优二叉搜索树的根节点编号。
具体实现过程请参考代码注释。