Egg Dropping Puzzle — DP Minimax (Floors from Trials)

eggs k = floors n = trial 0

g[e][t] table — floors coverable

g[e][t] = g[e−1][t−1] + g[e][t−1] + 1

egg row k current trial t cell being filled reached n (answer)

Result

eggs k

floors n

100

g[k][t] so far

min trials

—

Optimal first-drop spine appears once g[k][t] reaches n.

Press Step to begin. Each trial adds a new column: g[e][t] = (floors below a break) + (floors above a survive) + (the drop itself).

How to read this animation

Rows are egg counts e (from k at the top down to 0); columns are trial budgets t.
Each cell g[e][t] is the maximum number of floors you can fully resolve with e eggs and t trials.
The recurrence g[e][t] = g[e-1][t-1] + g[e][t-1] + 1 means: floors below a breaking drop (one fewer egg, one fewer trial), plus floors above a surviving drop (same eggs, one fewer trial), plus the floor you dropped from.
The answer is the first trial column t where the top row g[k][t] reaches or exceeds n. That t is the minimum guaranteed number of drops.
The spine on the right lists the optimal first-drop floors assuming each egg keeps surviving — for 2 eggs and 100 floors these are 14, 27, 39, … with each gap one smaller than the last.

Try it: set eggs = 1 to see the linear scan (g[1][t] = t, so the answer equals n); set eggs = 7, floors = 100 to watch the table reach 100 in just 7 trials — the binary-search regime where extra eggs stop helping.

The bottom row g[0][t] stays at 0 for every t: with no eggs you can resolve no floors.
The cells fill high egg index first within each column, so each g[e][t] reads the previous trial's values — the correct update order for a rolling array.
The spine floors are computed as g[k-1][t*-1] + 1 above the running base, exactly the reconstruction described in senior.md.
For 2 eggs the spine gaps shrink by one each step (14, 13, 12, …) because each survive leaves one fewer trial, so the next safe jump is one floor smaller.
The answer column matches the closed form: for k = 2 it is the smallest t with t(t+1)/2 ≥ n; for k large it is ⌈log₂(n+1)⌉.
Use Step to watch one cell fill at a time (the narration shows the exact arithmetic), or Run to auto-advance; Reset rebuilds with the current eggs/floors inputs.
The cell highlighted in green is the one currently being computed; the top row is tinted blue, and the current trial column is tinted gold.

Self-contained visualization. This shows the trials reformulation (the dual): instead of asking "fewest trials for n floors", it asks "most floors coverable in t trials". For 2 eggs and 100 floors the answer is 14 (since 13·14/2 = 91 < 100 ≤ 105 = 14·15/2). See junior.md, middle.md, and professional.md for the proofs.

The minimax recurrence dp[e][f] = 1 + minₓ max(dp[e-1][x-1], dp[e][f-x]) and this dual g[e][t] = g[e-1][t-1] + g[e][t-1] + 1 compute the same answer from opposite axes: the recurrence indexes by floors and is O(k·n²); the dual indexes by trials and is O(k·log n) because the number of trials is tiny. The closed form g[e][t] = Σ C(t, i) for i = 1..e gives the same values, and for e = 2 it is the triangular number t(t+1)/2.