Egg Dropping Problem
What you'll learn: How to use dynamic programming to find the minimum number of trials needed to determine the critical floor using k eggs and n floors.
The Problem
Imagine you have k identical eggs and a building with n floors. There's a critical floor: drop an egg from that floor or above and it breaks; below that floor, it survives. Your goal is to find this critical floor using the fewest trials in the worst case. If an egg breaks, you lose it; if it survives, you can reuse it.
Why It's a DP Problem
This problem has overlapping subproblems (same egg/floor combinations recur) and optimal substructure (the optimal solution depends on optimal solutions to smaller subproblems).
The Core Idea
Define dp[eggs][floors] = minimum trials needed with eggs eggs and floors floors.
When you drop an egg from floor x:
- It breaks: You lose one egg and must check the
x-1floors below - It survives: You keep the egg and must check the
n-xfloors above
Since we want the worst case, we take the maximum of these two outcomes. To minimize trials, we try all possible floors x and pick the best.
The recurrence:
dp[k][n] = 1 + min(max(dp[k-1][x-1], dp[k][n-x])) for all x from 1 to n
Base cases:
dp[k][0] = 0(no floors = no trials)dp[k][1] = 1(one floor = one trial)dp[1][n] = n(one egg = must try linearly from bottom)
Example
With 2 eggs and 10 floors, optimal strategy needs 4 trials in the worst case (not 10!).
Key Takeaway: The Egg Dropping Problem uses DP to minimize worst-case trials by considering all possible drop points and building solutions from smaller subproblems, trading off the risk of breaking vs. gaining information.