Перейти к: навигация, поиск
```from typing import List

class Solution(object):
def superEggDrop(self, K, N):

drops_for_previous_num_eggs = [i for i in range(N + 1)]

for num_eggs in range(2, K + 1):
drops_for_current_num_eggs = [None for _ in range(N + 1)]
drops_for_current_num_eggs[0] = 0

drop_floor = 1

for target_floor in range(1, N + 1):

while (
drop_floor < target_floor and
# If one use the method here, she/he is going to exceed time limit
# self.is_split_better_than_previous(floor, drop_floor, drops_for_previous_num_eggs, drops_for_current_num_eggs)
max(
drops_for_previous_num_eggs[drop_floor - 1],
drops_for_current_num_eggs[target_floor - (drop_floor - 1) - 1]
) > max(
drops_for_previous_num_eggs[drop_floor],
drops_for_current_num_eggs[target_floor - drop_floor - 1]
)
):
drop_floor += 1

drops_for_current_num_eggs[target_floor] = (
# Same here concerning time limit
# 1 + self.get_drops_for_floor(floor, drop_floor - 1, drops_for_previous_num_eggs, drops_for_current_num_eggs)
1 + max(
drops_for_previous_num_eggs[drop_floor - 1],
drops_for_current_num_eggs[target_floor - (drop_floor - 1) - 1]
)
)

drops_for_previous_num_eggs = drops_for_current_num_eggs

return drops_for_previous_num_eggs[-1]

def is_split_better_than_previous(
self,
floor: int,
drop_floor: int,
drops_for_previous_num_eggs: List[int],
drops_for_current_num_eggs: List[int]) -> bool:

return (
self.get_drops_for_floor(
floor,
drop_floor - 1,
drops_for_previous_num_eggs,
drops_for_current_num_eggs
) > self.get_drops_for_floor(
floor,
drop_floor,
drops_for_previous_num_eggs,
drops_for_current_num_eggs
)
)

def get_drops_for_floor(
self,
floor: int,
drop_floor: int,
drops_for_previous_num_eggs: List[int],
drops_for_current_num_eggs: List[int]) -> int:

return max(
drops_for_previous_num_eggs[drop_floor],
drops_for_current_num_eggs[floor - drop_floor - 1]
)```