Editing Dynamic programming (section)

=== Egg dropping puzzle ===
The following is a description of the instance of this famous [[puzzle]] involving N=2 eggs and a building with H=36 floors:<ref>Konhauser J.D.E., Velleman, D., and Wagon, S. (1996). [https://books.google.com/books?id=ElSi5V5uS2MC Which way did the Bicycle Go?] Dolciani Mathematical Expositions – No 18.  [[The Mathematical Association of America]].</ref> 
:Suppose that we wish to know which stories in a 36-story building are safe to drop eggs from, and which will cause the eggs to break on landing (using [[U.S. English]] terminology, in which the first floor is at ground level). We make a few assumptions:

:* An egg that survives a fall can be used again.
:* A broken egg must be discarded.
:* The effect of a fall is the same for all eggs.
:* If an egg breaks when dropped, then it would break if dropped from a higher window.
:* If an egg survives a fall, then it would survive a shorter fall.
:* It is not ruled out that the first-floor windows break eggs, nor is it ruled out that eggs can survive the 36th-floor windows.

: If only one egg is available and we wish to be sure of obtaining the right result, the experiment can be carried out in only one way. Drop the egg from the first-floor window; if it survives, drop it from the second-floor window. Continue upward until it breaks. In the worst case, this method may require 36 droppings. Suppose 2 eggs are available. What is the lowest number of egg-droppings that is guaranteed to work in all cases?

To derive a dynamic programming [[Bellman equation|functional equation]] for this puzzle, let the '''state''' of the dynamic programming model be a pair s = (n,k), where

: ''n'' = number of test eggs available, ''n'' = 0, 1, 2, 3, ..., ''N''&nbsp;&minus;&nbsp;1.
: ''k'' = number of (consecutive) floors yet to be tested, ''k'' = 0, 1, 2, ..., ''H''&nbsp;&minus;&nbsp;1.

For instance, ''s'' = (2,6) indicates that two test eggs are available and 6 (consecutive) floors are yet to be tested. The initial state of the process is ''s'' = (''N'',''H'') where ''N'' denotes the number of test eggs available at the commencement of the experiment. The process terminates either when there are no more test eggs (''n'' = 0) or when ''k'' = 0, whichever occurs first. If termination occurs at state ''s'' = (0,''k'') and ''k''&nbsp;>&nbsp;0, then the test failed.

Now, let

: ''W''(''n'',''k'') = minimum number of trials required to identify the value of the critical floor under the worst-case scenario given that the process is in state ''s'' = (''n'',''k'').

Then it can be shown that<ref name="sniedovich_03">{{Cite journal|doi = 10.1287/ited.4.1.48|title = OR/MS Games: 4. The Joy of Egg-Dropping in Braunschweig and Hong Kong|year = 2003|last1 = Sniedovich| first1 = Moshe|journal = INFORMS Transactions on Education|volume = 4| issue=1 |pages = 48–64|doi-access = free}}</ref>

: ''W''(''n'',''k'') = 1 + min{max(''W''(''n'' &minus; 1, ''x'' &minus; 1), ''W''(''n'',''k'' &minus; ''x'')): ''x'' = 1, 2, ..., ''k'' }

with ''W''(''n'',0) = 0 for all ''n''&nbsp;>&nbsp;0 and ''W''(1,''k'') = ''k'' for all&nbsp;''k''. It is easy to solve this equation iteratively by systematically increasing the values of ''n'' and&nbsp;''k''.

==== 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>