We can solve this problem using a dynamic programming approach. Let’s denote the minimum number of trials required for the worst case to find the critical floor with n eggs and k floors as T(n, k). There are 2 possibilities for each trial:
1. The egg breaks, and we are left with n − 1 eggs and have to check the remaining k − 1 floors below.
2. The egg doesn’t break, and we still have n eggs but only have to check the remaining k − x floors above.
For each floor x, 1 ≤ x ≤ k, we can take the maximum of these two possibilities, and select the minimum of these maximums over all floors x. That is, we can define T(n, k) as follows:
$$T(n, k) =
\begin{cases}
k & \text{if } n = 1 \\
0 & \text{if } k \in\{0,1\}\} \\
1 + \min_{1 \leq x \leq k} \{\max(T(n - 1, x - 1), T(n, k - x)) \} & \text{otherwise}
\end{cases}$$
The answer we are looking for is the value of T(2, 100). This problem exhibits overlapping subproblems, so we can solve it using the tabulation method by solving it in a bottom-up fashion. We can start by setting up a table of size 2 + 1 (rows) × 100 + 1 (columns) for solving the subproblems and computing the final answer. Here’s a Python code snippet that solves the problem using dynamic programming:
def egg_drop(eggs, floors):
T = [[0 for x in range(floors+1)] for x in range(eggs+1)]
# If there's only one floor, the required number of trials is 1
# If there's no floors at all, the required number of trials is 0
for egg in range(1, eggs+1):
T[egg][1] = 1
T[egg][0] = 0
# If there's only one egg, the worst case is having to drop it every floor
for floor in range(1, floors+1):
T[1][floor] = floor
for egg in range(2, eggs+1):
for floor in range(2, floors+1):
T[egg][floor] = float('inf')
for idx in range(1, floor+1):
res = 1 + max(T[egg-1][idx-1], T[egg][floor-idx])
T[egg][floor] = min(res, T[egg][floor])
return T[eggs][floors]
result = egg_drop(2, 100)The result is 14, which means the minimum number of drops needed to determine the highest floor from which an egg can be dropped without breaking with 2 eggs and a 100-story building is 14.