假设我有n个盒子，每个盒子里面都有一些值b[i]。我可以保证一个盒子的数组排序，使b[1] <= b[2] <= ... <= b[n]。我还可以保证有一个元素b[i] = x，我想找到x所在的盒子。抓住的是打开每个盒子b[i]有一些成本c[i]。
问题是如何最大限度地降低寻找x的总成本？我的直观方法是在b[i]上进行二分查找。这减少了操作总数（因为我得到了O（logn）比较），但我不能确切地看到这将如何最小化总成本。
很明显，只选择最便宜的盒子并继续使用是行不通的，因为在最坏的情况下我会打开每个盒子。关于如何改进这个或如何证明我的方法是最优/非最优的任何想法？
使用动态编程来查找最佳决策树。让T(i, j)成为搜索位置i..j的最坏情况。然后
T(i, j) = { 0, if i > j;
{ min_{k=i}^j (c[k] + max(T(i, k-1), T(k+1, j))), otherwise.
记住每个区间的k的最佳选择。
运行时间是O(n^3)，使用Knuth诀窍为O(n^2)减少到optimal BST。