有什么更好的方法来解决这个（贪心？）问题
What are some better approaches to this (greedy?) problem
假设我有 n 个盒子，每个盒子里面都有一些值 b[i]。我可以保证对一组框进行排序，使得 b[1] <= b[2] <= ... <= b[n]。我也可以保证有一个元素 b[i] = x 并且我想找到哪个盒子 x 在里面。问题是打开每个盒子 b[i] 有一些成本 c[i] .
问题是如何才能将查找 x 的总成本降至最低？我的直觉方法是对 b[i] 进行二进制搜索。这减少了操作总数（因为我得到了 O(logn) 比较）但我无法确切地看到这将如何最小化总成本。
显然，只挑选最便宜的盒子并继续是行不通的，因为在最坏的情况下我会打开每个盒子。关于如何改进这个或如何证明我的方法是 optimal/not 最优的有什么想法吗？
使用动态规划寻找最优决策树。设 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 的 optimal BST 技巧可以减少到 O(n^2)。
假设我有 n 个盒子，每个盒子里面都有一些值 b[i]。我可以保证对一组框进行排序，使得 b[1] <= b[2] <= ... <= b[n]。我也可以保证有一个元素 b[i] = x 并且我想找到哪个盒子 x 在里面。问题是打开每个盒子 b[i] 有一些成本 c[i] .
问题是如何才能将查找 x 的总成本降至最低？我的直觉方法是对 b[i] 进行二进制搜索。这减少了操作总数（因为我得到了 O(logn) 比较）但我无法确切地看到这将如何最小化总成本。
显然，只挑选最便宜的盒子并继续是行不通的，因为在最坏的情况下我会打开每个盒子。关于如何改进这个或如何证明我的方法是 optimal/not 最优的有什么想法吗？
使用动态规划寻找最优决策树。设 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 的 optimal BST 技巧可以减少到 O(n^2)。