The idea: drops in the worst case

You have a few identical eggs and a building with f floors. Somewhere there is a critical floor c: an egg dropped from floor c or higher breaks, an egg dropped from below c survives and can be used again. Maybe no floor breaks it at all. You must find c for sure. The question is the fewest drops that are enough in the worst case, wherever c turns out to be.

A building of 11 floors with e eggs. One drop from floor x = 4 splits it: if the egg survives, c is above x and f − x floors are left with e eggs, costing dp[e][f − x] more drops; if it breaks, c is x or below and x − 1 floors are left with e − 1 eggs, costing dp[e − 1][x − 1] more drops. dp[e][f] = 1 + min over x of the larger of the two.
One drop from floor x leaves one of two smaller puzzles; you don't choose which, so you plan for the larger.

One egg: floor by floor

With a single egg you cannot take any risk. If you drop it from floor 5 and it breaks, c could be 1, 2, 3, 4 or 5, and you have nothing left to test with. So you drop from floor 1, then 2, then 3, until it breaks. With f floors that is f drops in the worst case. (Demo: 1 egg, 10 floors)

The recurrence

Let dp[e][f] be the fewest drops that always find c with e eggs and f unknown floors. Drop the first egg from floor x. Two things can happen:

  • It breaks: c is x or lower. The x − 1 floors below are still unknown and you have e − 1 eggs: dp[e−1][x−1] more drops.
  • It survives: c is above x. The f − x floors above are unknown and you still have e eggs: dp[e][f−x] more drops.

The egg decides which branch happens, so a guarantee must cover the max of the two. You choose x, so you take the min over all x:

dp[e][0] = 0                       no unknown floor left
dp[1][f] = f                       one egg: floor by floor
dp[e][f] = 1 + min over x = 1..f of max( dp[e-1][x-1],    it breaks
                                         dp[e][f-x] )     it survives

Each cell reads cells with fewer floors or fewer eggs, so the table fills row by row, left to right. On the canvas the cell being filled is orange, the "breaks" cell of the best x is blue and the "survives" cell is green; the line under the table lists the worst case for every x.

Two eggs, ten floors: 4 drops

With 2 eggs the first egg can jump ahead, and the second egg checks the gap floor by floor after the first one breaks. For 10 floors the best first drop is floor 4: if it breaks, floors 1–3 take 3 more drops with one egg; if not, 6 floors are left with 2 eggs, which take 3 more drops. So dp[2][10] = 4, against 10 with one egg. (Demo: 2 eggs, 10 floors)

Playing the table

The table also gives the strategy. At each drop look up the cell for the eggs left and the floors still unknown, and drop from that cell's best x, counted from the highest floor known to be safe. When the egg breaks, the floors from there up turn red; when it survives, the floors up to there turn green. When no unknown floor is left, c is the floor just above the highest safe one. The number of drops never goes over dp[E][F], and for some c it is exactly that.

For 2 eggs and 100 floors, dp[2][100] = 14. Several first drops reach 14 (any floor from 9 to 14); the page takes the highest, so while the egg survives the drops go to floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100: each jump is one floor shorter than the last, because one drop has been used up. If the egg breaks at 50, the second egg checks 40–49 one by one: 4 + 10 = 14 drops. (Demo: 2 eggs, 100 floors)

The moves form: how many floors can m drops cover?

Turn the question around. Let F(m, e) be the most floors that m drops and e eggs can always settle. The first drop goes to some floor. If the egg breaks, the floors below it must be settled with m − 1 drops and e − 1 eggs, so at most F(m−1, e−1) floors may lie below it. If it survives, at most F(m−1, e) floors may lie above. Counting the floor of the drop itself:

F(m, e) = F(m-1, e-1) + 1 + F(m-1, e),      F(0, e) = F(m, 0) = 0
A building stacked from three parts: F(m−1, e−1) floors below the first drop, checked with m − 1 drops and e − 1 eggs if it breaks; the floor of the first drop; and F(m−1, e) floors above, checked with m − 1 drops and e eggs if it survives. A table for 2 eggs gives F(m, 2) = m(m+1)/2: 1, 3, 6, 10, …, 55, 78, 91 for m = 13, and 105 for m = 14, the first value at least 100.
m drops cover the floors below the first drop, that floor, and the floors above; with 2 eggs 14 drops cover 105 floors, 13 cover only 91.

So dp[e][f] is the smallest m with F(m, e) ≥ f, and the first drop goes to floor F(m−1, e−1) + 1. With one egg F(m, 1) = m. With two, F(m, 2) = m(m+1)/2, so 13 drops cover 91 floors and 14 cover 105: dp[2][100] = 14 and the first drop is F(13, 1) + 1 = 14. With three eggs F(m, 3) = 1, 3, 7, 14, 25, 41, 63, 92, 129, so 4 drops settle 14 floors and 9 drops settle 100. (Demo: 3 eggs, 14 floors)

The demos in numbers

eggsfloorsdpfirst drophidden cdrops used
1101011010
2104434 (4 ✗, 1, 2, 3 ✗)
210014145014 (14, 27, 39, 50 ✗, 40–49)
3144794 (7, 11 ✗, 9 ✗, 8)

Running time

The table has E × (F + 1) cells and each tries up to F floors, so filling it takes O(E·F²) time. Because dp[e−1][x−1] grows with x and dp[e][f−x] shrinks, the best x can be found by binary search, which gives O(E·F log F). The moves form is faster still: fill F(m, e) for m = 1, 2, … until it reaches F, which takes O(E·m) time for the answer m. With unlimited eggs the answer is the number of steps of binary search, about log₂(F + 1).

See also 0/1 Knapsack and Matrix Chain Multiplication, two more tables where each cell takes the best of several choices made from smaller cells.

What the page leaves out

The page is capped at 3 eggs and 100 floors so the table fits on the canvas. It leaves out the binary-search speed-up of the recurrence, the memoized top-down version, the average number of drops (here only the worst case counts), eggs that weaken after surviving a drop, and the closed form of F(m, e) as a sum of binomial coefficients.