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.

1. Problem Analysis

This is LeetCode problem 887: "Super Egg Drop". Here is the problem description:

You have a building with N floors, numbered from 1 to N, and you are given K eggs (K is at least 1). You need to determine a floor 0 <= F <= N where if you drop an egg from this floor, it won't break. Any higher floor will cause the egg to break, and any lower floor will not. If an egg doesn't break, you can reuse it for more drops. The question is, in the worst-case scenario, what is the minimum number of attempts you need to make to find this floor F?

This means you need to find the highest floor F from which an egg won't break. But what does it mean to make the minimum number of attempts in the worst-case scenario? Let's illustrate with some examples.

For instance, if we ignore the limitation on the number of eggs, and there are 7 floors, how would you identify the floor where the egg just breaks?

The most straightforward method is linear scanning: throw an egg from the 1st floor, if it doesn't break, go to the 2nd floor, throw it again, if it still doesn't break, go to the 3rd floor...

With this strategy, the worst-case scenario would be that the egg doesn't break until the 7th floor (F = 7), meaning you have made 7 attempts.

Now you should understand what "worst-case scenario" means: the egg breaking always happens at the end of the search interval. It won't break on the 1st floor; that would be good luck, not the worst-case scenario.

Now let's understand what "minimum number of attempts" means. Still ignoring the limitation on the number of eggs, with the same 7 floors, we can optimize the strategy.

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

If it breaks, it means F is less than 4, so try the (1 + 3) / 2 = 2 floor...

If it doesn't break, it means F is greater than or equal to 4, so try the (5 + 7) / 2 = 6 floor...

With this strategy, the worst-case scenario is that the egg doesn't break until the 7th floor (F = 7), or it always breaks until the 1st floor (F = 0). However, in either worst-case scenario, you only need to attempt ceil(log7) times, which equals 3, fewer than the 7 attempts before. This is what is meant by the minimum number of attempts.

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?