210. Egg Dropping Problem

Given a number of identical eggs and a number of floors in a building, find the minimum number of egg drops needed, in the worst case, to determine the exact floor below which eggs never break and at or above which they always do (assume such a threshold floor exists).

Input: Two lines: the first contains the number of eggs, the second contains the number of floors. Output: Print a single integer - the minimum number of trials needed in the worst case.

1 <= eggs <= 30, 1 <= floors <= 200

The phrase 'in the WORST case' is the key detail driving the whole recurrence - you must plan for the egg-breaks scenario AND the egg-survives scenario each time, taking whichever is WORSE, since you don't get to know in advance which will happen.

Find the minimum number of egg drops needed, in the worst case, to find the exact floor threshold below which eggs never break. Brute force: Try every possible sequence of drop choices directly and compute the worst-case trial count for each strategy - this branches combinatorially without memoization, since the same (eggs remaining, floors remaining) sub-problem recurs across many different strategies. Optimised: Memoizing on (eggs, floors) - since the worst-case trial count for a given number of eggs and floors doesn't depend on HOW you got there, only on those two numbers - avoids recomputing the same sub-problem repeatedly, and trying every possible first-drop floor x to MINIMIZE the resulting worst case is exactly what makes the strategy OPTIMAL rather than just feasible.

Define solve(eggs, floors) as the worst-case minimum number of drops needed, and for every possible floor choice from 1 to floors, recursively consider both outcomes of dropping an egg there: it breaks, leaving solve(eggs-1, choice-1) to determine floors below, or it survives, leaving solve(eggs, floors-choice) for floors above; take the worse (larger) of the two, add 1 for the current drop, and minimize this over all choices. This directly implements the problem's recursive definition and is correct, but without any caching the same (eggs, floors) subproblems get recomputed enormous numbers of times as the recursion branches. Time: Exponential in floors Space: O(eggs * floors) recursion depth

Flip the question around: instead of asking the minimum drops for a given number of floors, define dp[e][t] as the maximum number of floors that can be definitively resolved using e eggs and at most t trials, with the recurrence dp[e][t] = dp[e-1][t-1] + dp[e][t-1] + 1 (the drop either breaks, ruling out dp[e-1][t-1] floors below, or survives, ruling out dp[e][t-1] floors below, plus the floor just tested). Increase t starting from 0 until dp[eggs][t] is at least the number of floors, and that t is the answer. This removes the inner scan over every possible drop floor that the previous approach needed, since each cell is now filled in O(1) from two previously computed cells, cutting a full factor of floors off the running time. Time: O(eggs * floors) Space: O(eggs * floors)

Use the exact same recurrence as the brute-force version, but cache every computed solve(eggs, floors) value in a table so each distinct (eggs, floors) pair is solved only once no matter how many times it's needed elsewhere in the recursion. This eliminates all the redundant recomputation of the brute-force approach, and since there are only eggs*floors distinct subproblems each requiring an O(floors) scan over drop choices, the total work becomes a manageable polynomial. Time: O(eggs * floors^2) Space: O(eggs * floors)

1. dp[e][f] = minimum trials needed with e eggs and f floors. 2. Trying a drop from floor x splits into two cases: the egg BREAKS (recurse with e-1 eggs, x-1 floors below) or it DOESN'T (recurse with e eggs, f-x floors above) - take the WORSE of the two plus 1 (accounting for this drop), then pick x to MINIMIZE that worst case. 3. Try every possible floor x to drop from, choosing whichever minimizes the guaranteed worst-case trial count.

Time: O(eggs * floors²) with the straightforward DP (trying every floor x for each (e,f) state); a more advanced binary-search-on-x or a different DP formulation (trials as the state instead of floors) can improve this to O(eggs * floors * log(floors)) or even O(eggs * log(floors)). Space: O(eggs * floors), for the DP table.

Test eggs = 1 (must test floors one by one, worst case equals floors) and the upper bounds eggs = 30, floors = 200.

Be ready to mention the more advanced 'flip the DP dimensions' technique (dp[e][trials] = max floors distinguishable with e eggs and a given number of trials) as a way to reduce this from O(floors²) to O(floors) per egg count - a well-known, elegant optimization for this classic problem.