请完成最优二分检索树的代码
时间: 2024-05-01 22:21:20 浏览: 21
以下是最优二分检索树的 Python 代码:
```python
def optimal_bst(p, q, n):
e = [[0] * (n + 1) for i in range(n + 1)]
w = [[0] * (n + 1) for i in range(n + 1)]
root = [[0] * n for i in range(n)]
for i in range(n + 1):
e[i][i - 1] = q[i - 1]
w[i][i - 1] = q[i - 1]
for l in range(1, n + 1):
for i in range(n - l + 1):
j = i + l - 1
e[i][j] = float('inf')
w[i][j] = w[i][j - 1] + p[j] + q[j]
for r in range(i, j + 1):
t = e[i][r - 1] + e[r + 1][j] + w[i][j]
if t < e[i][j]:
e[i][j] = t
root[i][j - 1] = r
return e[0][n - 1], root
```
其中,`p` 和 `q` 分别是节点的概率和虚拟节点的概率,`n` 是节点的数量。返回值是最小期望代价和和根节点数组 `root`。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)