Classic DP: Egg Drop

This article discusses a classic algorithm problem: given several floors and several eggs, you need to determine the minimum number of attempts required to find the highest floor from which an egg can be dropped without breaking. This problem is frequently asked in interviews at major Chinese companies as well as Google and Facebook. However, they often change the context to throwing cups or bowls instead of eggs to avoid wastage.

We'll get to the specific problem shortly. This problem has numerous solution techniques, including several different dynamic programming approaches with varying efficiencies, and finally, an extremely efficient mathematical solution. Consistent with the style of this book, we avoid overly complex techniques that are not broadly applicable, as they are not worth the effort to learn.

Let's now use the general dynamic programming approach we've emphasized to analyze this problem.

Section 1: Problem Analysis

This is LeetCode problem #887, "Egg Drop." Let me describe the problem:

You are in front of a building with N floors, numbered from 1 to N. You are given K eggs (K is at least 1). There is a floor 0 <= F <= N in this building where, if you drop an egg from this floor, it will not break (eggs will break on any floor higher than F, and will not break on any floor lower than F. If an egg does not break, you can pick it up and drop it again). The question is, in the worst-case scenario, what is the minimum number of times you need to drop an egg to determine this floor F?

In other words, you need to find the highest floor F where the egg does not break. But what does it mean to find the "minimum" number of drops in the "worst-case" scenario? Let's illustrate with examples.

For instance, ignoring the limit on the number of eggs for now, suppose you have 7 floors. How would you find the exact floor where the egg breaks?

The most primitive method is linear scanning: drop an egg from the 1st floor, if it doesn't break, go to the 2nd floor, and so on.

With this strategy, the worst-case scenario is that you try up to the 7th floor and the egg still doesn't break (F = 7), meaning you have dropped the egg 7 times.

Now you should understand what "worst-case" scenario means: the egg breaking always occurs when the search range is exhausted, not when you luckily break the egg on the first floor.

Next, let's understand what it means to drop the egg the "minimum" number of times. Still ignoring the limit on the number of eggs, and with the same 7 floors, we can optimize our strategy.

The best strategy is to use binary search. First, drop an egg from the (1 + 7) / 2 = 4th floor:

• If it breaks, it means F is less than 4, so you try the (1 + 3) / 2 = 2nd floor...
• If it doesn't break, it means F is greater than or equal to 4, so you try the (5 + 7) / 2 = 6th floor...

With this strategy, the worst-case scenario is either trying up to the 7th floor without breaking the egg (F = 7), or the egg breaking all the way down to the 1st floor (F = 0). However, in either worst-case scenario, you only need to try log7 times, rounded up to 3, which is fewer than the 7 attempts in the previous method. This is what is meant by the minimum number of drops.

In reality, if there were no limit on the number of eggs, a binary search approach would clearly yield the minimum number of attempts. However, the issue is that you are now given a limit K on the number of eggs, making the direct use of binary search impractical.

For example, if you only have 1 egg and 7 floors, would you dare to use binary search? If you drop the egg from the 4th floor and it doesn't break, you can pick it up and try higher floors. But if it breaks, you have no more eggs to continue testing, and you cannot determine the exact floor F where the egg would not break.

In such a scenario, you can only use a linear scan method, trying each floor from the bottom up. In the worst case, you would need to drop the egg 7 times, so the algorithm should return 7.

Some readers might think: since binary search is the fastest way to eliminate floors, why not use binary search first and switch to linear scanning when only 1 egg is left? Wouldn't that give the minimum number of drops?

Unfortunately, it doesn't. For instance, if you have 100 floors and 2 eggs, and you drop one from the 50th floor and it breaks, you would then need to linearly scan floors 1 to 49, resulting in a worst-case scenario of 50 drops.

If you replace "binary" with "quinary" or "decimal" search, it significantly reduces the worst-case number of attempts. For example, dropping the first egg every ten floors and then scanning linearly with the second egg would result in no more than 20 drops. The optimal solution is actually 14 drops. There are many optimal strategies, and they don't follow a clear pattern.

All this explanation is to ensure everyone understands the problem and recognizes its complexity. Even manually calculating it is challenging, so how can we solve it algorithmically?