动态规划--最优二叉搜索树

题目:

若4个关键字的概率如下表给出，求其最优二叉搜索树及最小期望搜索代价。

p1=0.14     p2=0.18       p3=0.08        p4=0.16   
q0=0.06     q1=0.11       q2=0.11         q3=0.06        q4=0.10   

答:

• 计算过程(手算)

  
  image.png
  image.png
  image.png

• 结论: 最后求出, 最小期望为2.41.

  
  image.png

这题目手算也是折磨人啊, 后面再详细分析下, 赶紧睡觉喽