Classic DP: Egg Drop
This article will resolve
| LeetCode | Difficulty |
|---|---|
| 887. Super 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 fact, if there is no limit on the number of eggs, the binary search approach can obviously yield the least number of attempts. However, the challenge is that you are now given a limit on the number of eggs, K, so directly using binary search is not feasible.
For instance, if you are given only 1 egg and a 7-story building, would you dare to use binary search? If you throw 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 cannot continue testing, and you won't be able to determine the exact floor F where the egg can be dropped without breaking.
In this situation, you can only use a linear scan method, trying each floor from the bottom up. In the worst case, this requires 7 throws, so the algorithm should return a result of 7.
Some readers might think: binary search is undoubtedly the fastest way to eliminate floors, so why not use binary search until only 1 egg is left, then perform a linear scan? Would this result in the minimum number of egg drops?
Unfortunately, it does not. For example, if you have a 100-story building and 2 eggs, dropping an egg from the 50th floor and it breaks, you would need to perform a linear scan from floors 1 to 49, resulting in 50 throws in the worst case.
If you forgo "binary" and use "quinary" or "decuple" divisions, it would significantly reduce the worst-case attempts. For example, if you drop the first egg every ten floors, and when it breaks, use the second egg for a linear scan, the total attempts would not exceed 20. The optimal solution is actually 14 attempts. There are many optimal strategies, and there is no obvious pattern.
After this lengthy explanation, I hope to ensure everyone understands the problem's meaning and recognizes its complexity. Even calculating manually is not easy, so how can it be solved algorithmically?