最优二叉搜索树算法流程图

最优二叉搜索树的算法流程图如下：

1. 初始化一个二维数组dp，用于保存子问题的最优解。
2. 根据输入的概率分布pi和qi，计算出两个一维数组p和q。
3. 对于每个节点i，计算其子树的概率和，并初始化dp[i][i]为qi。
4. 对于子树长度l=2到n，依次计算dp[i][i+l-1]，其中i为子树的根节点。
- 计算dp[i][i+l-1]的过程中，遍历所有可能的根节点j，计算以节点j为根节点的子树的代价。
- 代价的计算公式为：cost = sum(p[i..i+l-1]) + sum(q[i-1..i+l-1]) + dp[i][j-1] + dp[j+1][i+l-1]。
- 在遍历过程中，取最小的代价作为dp[i][i+l-1]的值。
5. 最终的最优解保存在dp[n]中，即整个树的代价。
6. 根据dp数组的记录，可以构造出最优二叉搜索树的结构。