# 经典动态规划：高楼扔鸡蛋

Info

**已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~**

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

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.

## 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 = 4`

th floor:

- If it breaks, it means
`F`

is less than 4, so you try the`(1 + 3) / 2 = 2`

nd floor... - If it doesn't break, it means
`F`

is greater than or equal to 4, so you try the`(5 + 7) / 2 = 6`

th 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?