给定n个互异的关键字组成的序列k=<k1,k2,...,kn>，且关键字有序（k1<k2<...<kn），从这些关键字中构造一棵二叉查找树。对每个关键字ki，每次搜索到的概率为pi。还有n+1个“虚拟键”d0,d1,...,dn，他们代表不在k的值。d0代表所有小于k1的值，dn代表所有大于kn的值，对于i = 1,2,...,n-1,虚拟键di代表位于ki和ki+1之间的值。对于每个di，每次搜索di的概率为qi。要求建立一棵最优二叉查找树，使所有的搜索操作访问的结点总数最少，并输出平均搜索每个结点的访问结点数的值。 输入描述 第一行n个实数p1,p2...pn， 表示k1,k2,...kn搜索到的概率。 第二行n+1个实数d0,d1,...dn, 表示 n+1个虚拟键搜索到的概率。 输出描述 一个实数，表示平均搜索每个结点的访问结点数的值。 输入样例 0.15 0.1 0.05 0.1 0.2 0.05 0.1 0.05 0.05 0.05 0.1 输出样例 一个实数，保留两位小数结果值。用python

""" 思路： 1. 动态规划解决问题 2. 设root[i][j]: i <= j, 二叉查找树的根节点是k[i]到k[j]的虚拟键 3. 设dp[i][j]： i <= j, 表示二叉查找树的期望代价 所以 dp[i][j] = min(dp[i][k-1] + dp[k+1][j]) + sum[p[i]...p[j]] 其中 k 是根节点 虚拟键可以通过下标在 dp[i][j] 中找到对应位置的代价 """ def optimalBST(p, q): n = len(p) # 初始化dp为0，表示还没有计算过对应位置的二叉查找树的期望代价 dp = [[0] * (n + 1) for _ in range(n + 1)] # 初始化二叉查找树的根节点 root = [[0] * (n + 1) for _ in range(n + 1)] # 初始化dp和root for i in range(1, n + 2): dp[i - 1][i - 1] = q[i - 1] root[i - 1][i - 1] = i - 1 # 计算dp和root for gap in range(1, n + 1): for i in range(n - gap + 1): j = i + gap dp[i][j] = float("inf") for k in range(i, j + 1): temp = dp[i][k - 1] + dp[k + 1][j] + sum(p[i:j+1]) + sum(q[i:j+2]) if temp < dp[i][j]: dp[i][j] = temp root[i][j] = k return dp[0][n], root if __name__ == "__main__": p = [0.15, 0.1, 0.05, 0.1, 0.2, 0.05, 0.1, 0.05, 0.05, 0.05, 0.1] q = [0.1, 0.05, 0.05, 0.05, 0.05, 0.1] avg_cost, root = optimalBST(p, q) print('{:.2f}'.format(avg_cost)) """ [2024-06-09 14:30:52 | AI写代码神器 | 857点数解答]