Super Egg Drop

Super Egg Drop sounds like a physics puzzle, but it is a dynamic-programming gem. The winning move is counter-intuitive: instead of computing the answer directly, you flip the question on its head and let a tiny table do the work.

The slow way first

The natural DP is drops(k, n) = pick a floor x, drop an egg, and take the worst of the two outcomes (it breaks → drops(k-1, x-1), it survives → drops(k, n-x)), then minimize over every choice of x. That is O(k · n²) — for each state you scan all n floors looking for the best drop. With large n it is far too slow, and the inner minimization is fiddly to get right.

The question to ask: what if the number of moves were the thing I controlled?

The idea: count floors per move, not drops per floor

Define dp[m][k] = the maximum number of floors you can fully resolve using at most m moves and k eggs. Now think about your first drop with m moves and k eggs in hand:

• If the egg breaks, you have m-1 moves and k-1 eggs to search the floors below → dp[m-1][k-1] floors.
• If the egg survives, you have m-1 moves and k eggs to search the floors above → dp[m-1][k] floors.
• Plus the 1 floor you just tested.

So dp[m][k] = dp[m-1][k-1] + dp[m-1][k] + 1. Grow m from 0 upward; the first m where dp[m][k] >= n is the answer.

This is O(k · m) where m is at most n, but usually far smaller — the floor count grows roughly like a polynomial in m, so it explodes quickly.

Walk through it

Step through the animation for k = 2, n = 6. Each row is a move count m; each column an egg count. Watch the table fill: one move covers 1 floor, two moves cover 3, and three moves with 2 eggs cover 6 — exactly our goal, so we stop at m = 3.

Pseudocode

dp[m][k] = max floors resolvable with m moves and k eggs
m = 0
while dp[m][k] < n:
    m = m + 1
    for eggs in 1..k:
        dp[m][eggs] = dp[m-1][eggs-1]   # egg breaks, search below
                    + dp[m-1][eggs]      # egg survives, search above
                    + 1                  # the floor we just tested
return m                                  # first m that covers n floors

The Python solution

def super_egg_drop(k, n):
    dp = [[0] * (k + 1) for _ in range(n + 1)]
    m = 0
    while dp[m][k] < n:
        m += 1
        for eggs in range(1, k + 1):
            dp[m][eggs] = (dp[m - 1][eggs - 1]
                           + dp[m - 1][eggs]
                           + 1)
    return m

• dp[m][eggs] is the most floors we can clear with m moves and eggs eggs. Row 0 is all zeros (0 moves clears 0 floors).
• We loop m upward, filling one whole row per move.
• The recurrence on lines 7-9 is the heart: breaks below + survives above + the 1 floor tested.
• dp[m - 1][eggs - 1] is the "egg broke" branch (one fewer egg), dp[m - 1][eggs] the "egg survived" branch (same eggs).
• We stop the moment dp[m][k] >= n and return that m — the minimum worst-case drops.

Complexity

Because the coverable floor count grows fast in m, the loop usually finishes in very few moves even for huge n. Collapsing dp to a single row drops the space to O(k).

When this pattern shows up

Practice