高德纳的最优二叉搜索树在 O(n^2)

Question

我正在尝试实现高德纳的最佳二叉搜索树，它可以在O(n^2(时间内运行。我有在 O(n^3( 中运行的代码。

float P[N + 1] = {0, .13, .12, .15, .05, .12, .10, .08, .09, .03, .13};
float sum[N + 1] = {0, .13, .25, .40, .45, .57, .67, .75, .84, .87, 1.00};
float M[N + 1][N + 1];
int root[N + 1][N + 1];
int s, i, j;
float temp;
for (s = 0; s <= N; s++){
for (i = 0; i <= N; i++){
M[s][i] = 0;
root[s][i] = 0;
}
}
for (s = 2; s <= N; s++){
for (i = 1; i <= N - s + 1; i++){
M[s][i] = N;
for (j = i; j <= i + s - 1; j++){
temp = M[j - i][i] + M[i + s - j - 1][j + 1]+ sum[i + s - 1] - sum[i - 1] - P[j];
if (M[s][i] > temp){
M[s][i] = temp;
root[s][i] = j;
}
}
}
}

M 是成本数组。P 是每个节点的概率。我从以下位置得到一些想法：动态规划：为什么高德纳改进为最优二叉搜索树 O(n^2(？。就我而言，我尝试将第三个循环从for (j = i; j <= i + s - 1; j++)修改为for (j = root[s+1][i]; j <= root[s][i-1]; j++).但它不起作用。有人可以给我一些关于这个问题的线索吗？

Answer 1

你应该按大小的非递减顺序计算最优子树的成本，所以当你填写 M[s][i] 时，---大小为 s 的子树的最小成本，其最左边的键有索引 i ---你还没有填写 M[s+1][i] 或根 [s+1][i]。

干杯 崔维斯

PS "j <= root[s][i-1]"也不太正确。