算法-最佳二叉树(OBST)

动态规划

Posted by MetaNetworks on November 7, 2019
本页面总访问量

参考

最佳二叉树——动态规划

符号定义

  • $e(i,j) \to$从第$i$个结点到第$j$个字符,查询的效率值
  • $w(i,j)\to \sum_{k=i}^{j}p(k)$
  • $p(k) \to$第$k$个字符在用户输入中出现的概率

公式: \(e(i,j)=\left\{ \begin{array}{lr} 0, & if~i=j+1\\ min_{i \le r \le j}\{e(i,r-1)+e(r+1,j)+w(i,j)\} & if~~~~~~~~i\le j \end{array} \right.\)