这是Robert Sedgewick的算法第4版的练习题1.4.24.
Suppose that you have an N-story building and plenty of eggs. Suppose also that
an egg is broken if it is thrown off floor F or higher, and unhurt otherwise.
First, devise a strategy to determine the value of F such that the number of
broken eggs is ~lgN when using ~lgN throws, then find a way to reduce the cost to
~2lgF.
虽然lgN解决方案很容易想到,但我完全不知道2lgF解决方案.无论如何,我们没有给出价值F,所以2lgF解决方案的基础是什么？
谁能对这个问题有所了解？谢谢.
这是"算法导论"第3版的练习15.5-4,这是关于Knuth对最优二叉搜索树的DP方法的改进.
最优二叉搜索树的DP算法是:
OPTIMAL_BST(p, q, n)
let e[1..n+1, 0..n], w[1..n+1, 0..n], and root[1..n, 1..n] be new tables
for i = 1 to n+1
e[i, i - 1] = q[i - 1];
w[i, i - 1] = q[i - 1];
for l = 1 to n
for i = 1 to n - l + 1
j = i + l - 1
e[i, j] = INFINITY
w[i, j] = w[i, j - 1] + p[j] + q[j]
for r = i …