-
Notifications
You must be signed in to change notification settings - Fork 4.7k
Expand file tree
/
Copy pathegg_drop.py
More file actions
52 lines (38 loc) · 1.21 KB
/
egg_drop.py
File metadata and controls
52 lines (38 loc) · 1.21 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
"""
Egg Drop Problem
Given K eggs and a building wi
5BEB
th N floors, determine the minimum number
of moves needed to find the critical floor F in the worst case.
Reference: https://en.wikipedia.org/wiki/Dynamic_programming#Egg_dropping_puzzle
Complexity:
Time: O(n * k^2)
Space: O(n * k)
"""
from __future__ import annotations
_INT_MAX = 32767
def egg_drop(n: int, k: int) -> int:
"""Find the minimum number of trials to identify the critical floor.
Args:
n: Number of eggs.
k: Number of floors.
Returns:
Minimum number of trials in the worst case.
Examples:
>>> egg_drop(1, 2)
2
>>> egg_drop(2, 6)
3
"""
egg_floor = [[0 for _ in range(k + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
egg_floor[i][1] = 1
egg_floor[i][0] = 0
for j in range(1, k + 1):
egg_floor[1][j] = j
for i in range(2, n + 1):
for j in range(2, k + 1):
egg_floor[i][j] = _INT_MAX
for x in range(1, j + 1):
res = 1 + max(egg_floor[i - 1][x - 1], egg_floor[i][j - x])
if res < egg_floor[i][j]:
egg_floor[i][j] = res
return egg_floor[n][k]