Course contentsShow
← Computer Science
Lesson 938 of 2,87222. Dynamic ProgrammingFree lesson

Egg Dropping Problem

Find minimum trials needed to determine critical floor with k eggs and n floors using DP.

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-1 floors below
  • It survives: You keep the egg and must check the n-x floors 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.