Editing Dynamic programming (section)

==== Faster DP solution using a different parametrization ====
Notice that the above solution takes <math>O( n k^2 )</math> time with a DP solution. This can be improved to <math>O( n k \log k )</math> time by binary searching on the optimal <math>x</math> in the above recurrence, since <math>W(n-1,x-1)</math> is increasing in <math>x</math> while <math>W(n,k-x)</math> is decreasing in <math>x</math>, thus a local minimum of <math>\max(W(n-1,x-1),W(n,k-x))</math> is a global minimum. Also, by storing the optimal <math>x</math> for each cell in the DP table and referring to its value for the previous cell, the optimal <math>x</math> for each cell can be found in constant time, improving it to <math>O( n k )</math> time. However, there is an even faster solution that involves a different parametrization of the problem:

Let <math>k</math> be the total number of floors such that the eggs break when dropped from the <math>k</math>th floor (The example above is equivalent to taking <math>k=37</math>).

Let <math>m</math> be the minimum floor from which the egg must be dropped to be broken.

Let <math>f(t,n)</math> be the maximum number of values of <math>m</math> that are distinguishable using <math>t</math> tries and <math>n</math> eggs.

Then <math>f(t,0) = f(0,n) = 1</math> for all <math>t,n \geq 0</math>.

Let <math>a</math> be the floor from which the first egg is dropped in the optimal strategy.

If the first egg broke, <math>m</math> is from <math>1</math> to <math>a</math> and distinguishable using at most <math>t-1</math> tries and <math>n-1</math> eggs.

If the first egg did not break, <math>m</math> is from <math>a+1</math> to <math>k</math> and distinguishable using <math>t-1</math> tries and <math>n</math> eggs.

Therefore, <math>f(t,n) = f(t-1,n-1) + f(t-1,n)</math>.

Then the problem is equivalent to finding the minimum <math>x</math> such that <math>f(x,n) \geq k</math>.

To do so, we could compute <math>\{ f(t,i) : 0 \leq i \leq n \}</math> in order of increasing <math>t</math>, which would take <math>O( n x )</math> time.

Thus, if we separately handle the case of <math>n=1</math>, the algorithm would take <math>O( n \sqrt{k} )</math> time.

But the recurrence relation can in fact be solved, giving <math>f(t,n) = \sum_{i=0}^{n}{ \binom{t}{i} }</math>, which can be computed in <math>O(n)</math> time using the identity <math>\binom{t}{i+1} = \binom{t}{i} \frac{t-i}{i+1}</math> for all <math>i \geq 0</math>.

Since <math>f(t,n) \leq f(t+1,n)</math> for all <math>t \geq 0</math>, we can binary search on <math>t</math> to find <math>x</math>, giving an <math>O( n \log k )</math> algorithm.<ref>{{Citation |author=Dean Connable Wills |title=Connections between combinatorics of permutations and algorithms and geometry |url=https://ir.library.oregonstate.edu/xmlui/handle/1957/11929?show=full}}</ref>