1. One-Liner
Egg drop minimizes worst-case number of drops to find the highest safe floor using k eggs and n floors—dp[e][f] with minimax over the first drop floor.
2. The Problem It Solves
You must discover the critical floor where eggs break, optimizing for worst case when outcomes (break or not) are adversarial. Classic minimax + DP interview staple.
3. The Core Idea
If you drop at floor x: either egg breaks → subproblem with e-1, x-1 floors; or survives → e eggs, f-x floors above. Take 1 + max of those, then minimize over x.
4. How It Works (Step-by-Step)
| Step | What Happens |
|---|---|
| 1 | Base: dp[1][f]=f, dp[e][0]=0, dp[e][1]=1 |
| 2 | For each e,f, try x from 1 to f |
| 3 | dp[e][f]=min_x (1+max(dp[e-1][x-1], dp[e][f-x])) |
| 4 | Optimize x with monotonicity → binary search possible |
5. Dry Run Example
k=1, n=10: must linear scan from bottom → 10 drops worst case.
6. Key Properties
| Property | Value |
|---|---|
| Recurrence | Minimax |
| Optimizations | BS on x, math for k=2 |
7. Where It Is Used
| Domain | Use |
|---|---|
| Interviews | Hard DP |
| Robotics | Sensor worst-case planning (analogy) |
8. Interview Tips
Know O(k·n²) naive; mention faster search on x; super egg LeetCode variant.
9. Comparison with Other Algorithms
| Problem | Flavor |
|---|---|
| Egg drop | Minimax |
| Binary search | Not directly—outcome-dependent |
10. Complexity
| Metric | Value |
|---|---|
| Time | O(k·n²) naive inner minimization |
| Space | O(k·n) |
Implementation Example (PYTHON)
def egg_drop(k: int, n: int) -> int:
dp = [[0] * (n + 1) for _ in range(k + 1)]
for f in range(n + 1):
dp[1][f] = f
for e in range(2, k + 1):
for f in range(1, n + 1):
dp[e][f] = min(
1 + max(dp[e - 1][x - 1], dp[e][f - x]) for x in range(1, f + 1))
return dp[k][n]