最佳二叉树——动态规划
符号定义
- $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.\)
