动态规划法求最优二分检索树代码

以下是使用动态规划法求解最优二分检索树的代码实现：

def optimal_bst(p, q, n):
    # 初始化二维数组e和w
    e = [[0] * (n + 1) for _ in range(n + 1)]
    w = [[0] * (n + 1) for _ in range(n + 1)]
    
    # 计算w和e的初始值
    for i in range(1, n + 1):
        w[i][i - 1] = q[i - 1]
        e[i][i - 1] = q[i - 1]
    
    # 计算w和e的值
    for l in range(n):
        for i in range(1, n - l + 1):
            j = i + l - 1
            w[i][j] = w[i][j - 1] + p[j] + q[j]
            e[i][j] = float('inf')
            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
    
    # 返回最优根节点的期望代价
    return e[1][n]

其中，p和q分别表示每个关键字被查找的概率和不在树中出现的概率，n表示关键字的个数。函数返回最优根节点的期望代价。