如果我們想寫一個單詞查詢的軟體的話，我們的目的就是讓查詢的總時間最短，我們首先想到用之前的二叉查找樹。我們可以用紅黑樹或者其它的平衡二叉樹來保證每個單詞的搜尋時間。但是每個單詞出現的頻率一般不同，是以我們希望把頻率較大的單詞放在離根比較近的地方，頻率較小的放在離葉子較近的地方。而且，我們所要查詢的單詞詞庫中沒有，這也值得考慮。
由上文可知，ki表示單詞，di表示不能查到的情況。由上面的例子可知，一棵最優二叉樹不一定是高度最小的樹。我們也不一定總把頻率最大的放在根部。
和矩陣鍊乘法一樣，窮舉所有的可能行肯定不是一個好的算法。由于具有動态規劃的特征，毫無疑問，我們将使用動态規劃法。
對于原序列，我們假設第k個元素(采用周遊的方法)作為根時可以得到最優解，由于是二叉查詢樹，則前k-1個元素在左子樹，剩餘元素在右子樹。接下來，我們要分别在左、右子樹中找到最優二叉樹，于是我們可以用相同的方法：假設左、右子樹中第m，n個為根時，可以得到最優解，依此類推，就可以求得整體最優解。上面的解法中，可能存在左或者右子樹為空的情況：
通過推導，可以遞推公式：
其中e表示搜尋的代價，q[i]為d[i]的出現頻率，w為子樹總的機率。
具體程式實作如下：
上述程式運作後，數組e,w,root的結果如下：
上述程式的運作時間為O（n^3）,這和前面的矩陣鍊乘法是一樣的。
作者：nineheadedbird