Задача о падающих яйцах (Super Egg Drop): от O(k·n²) до O(k log n)
Разбор задачи о яйцах и этажах: ДП O(k·n²), бинпоиск по точке броска, переворот состояния dp[m][k] и формула через биномиальные коэффициенты. Код на Python и JavaScript.
Коротко
| Подход | Время | Память | Когда годится |
|---|---|---|---|
| ДП «яйца × этажи», перебор броска | , объяснить идею | ||
| То же + бинпоиск по точке броска | проходит LeetCode, но громоздко | ||
Переворот: dp[m][k] — этажи | , | основное решение на собеседовании | |
| Сумма биномов + бинпоиск по | красивый финал, follow-up |
- Главная мысль: вместо «сколько бросков нужно на этажей» спрашиваем «сколько этажей можно проверить за бросков».
- Переход после переворота: .
- Ответ для 2 яиц и 100 этажей — 14 бросков, первый бросок с 14-го этажа.
Постановка
У вас одинаковых яиц и здание из этажей. Существует неизвестный этаж (): яйцо, брошенное с этажа выше , разбивается, а с этажа и ниже — остаётся целым. Целое яйцо можно бросать снова, разбитое — нет.
Нужно найти минимальное число бросков, которое гарантированно (в худшем случае) определяет .
Это LeetCode 887 «Super Egg Drop» (Hard), ограничения , . Двухъяичная версия (LeetCode 1884, «Egg Drop With 2 Eggs and N Floors») — классическая головоломка, которую любят спрашивать устно.
Примеры:
- → 2. С одним яйцом рисковать нельзя: бросаем с 1-го, потом со 2-го.
- → 3.
- → 4.
- → 14.
Интуиция: почему не бинпоиск
Первая мысль — обычный бинарный поиск: бросить с 50-го, потом с 25-го или 75-го и так далее. С бесконечным числом яиц это и есть ответ: бросков. Но яиц мало. Если с двумя яйцами бросить с 50-го и разбить, второе яйцо придётся вести с 1-го этажа вверх по одному — до 49 бросков в худшем случае.
С одним яйцом выбора нет вообще: только линейный перебор, бросков. Значит, ответ живёт между и , и всё определяется балансом: насколько рискованно бросать «высоко», если разбитое яйцо отнимает инструмент.
Решение 1: ДП «яйца × этажи» за O(k·n²)
Пусть — минимум бросков, чтобы гарантированно найти при яйцах и «подозрительных» этажах. Абсолютная высота не важна: важно лишь, сколько этажей осталось проверить.
Бросаем с этажа (). Два исхода:
- Разбилось. Ответ ниже : осталось яиц и этажей.
- Уцелело. Ответ выше: яиц и этажей.
Мы не знаем, какой исход выпадет, поэтому готовимся к худшему и берём максимум. А этаж выбираем сами — берём минимум:
Базы: (проверять нечего), (одно яйцо — перебор снизу).
def egg_drop_naive(k: int, n: int) -> int: # dp[e][f] — минимум бросков для e яиц и f этажей dp = [[0] * (n + 1) for _ in range(k + 1)] for f in range(1, n + 1): dp[1][f] = f # одно яйцо — только линейный перебор for e in range(2, k + 1): for f in range(1, n + 1): best = f for x in range(1, f + 1): worst = 1 + max(dp[e - 1][x - 1], dp[e][f - x]) best = min(best, worst) dp[e][f] = best return dp[k][n] print(egg_drop_naive(2, 6)) # 3 print(egg_drop_naive(2, 100)) # 14
Состояний , на каждое — перебор точек броска: . Для , это операций — не пройдёт. Но с этого решения стоит начинать на собеседовании: оно честно выводится из постановки и показывает, что вы видите «минимакс» — мы минимизируем по своему выбору и максимизируем по выбору противника (природы).
Пример: 2 яйца, 6 этажей
Посчитаем вручную. Строка для одного яйца тривиальна: . Строка для двух яиц до уже готова: . Перебираем точку первого броска:
| разбилось: | уцелело: | ||
|---|---|---|---|
| 1 | 0 | 3 | 4 |
| 2 | 1 | 3 | 4 |
| 3 | 2 | 2 | 3 |
| 4 | 3 | 2 | 4 |
| 5 | 4 | 1 | 5 |
| 6 | 5 | 0 | 6 |
Минимум — 3, при броске с 3-го этажа. Видно и форму «галочки»: левый столбец растёт, средний убывает, а лучший — там, где они встречаются. Это наблюдение и даст следующую оптимизацию.
Если динамика пока даётся тяжело, сначала разберите ДП для начинающих и задачу о размене монет — там та же логика «перебираем последний шаг».
Решение 2: бинпоиск по точке броска, O(k·n log n)
Посмотрим на два слагаемых под максимумом как на функции от при фиксированных и :
- — не убывает по : чем выше бросаем, тем больше этажей под нами, тем больше работы, если разобьётся.
- — не возрастает по : чем выше бросаем, тем меньше этажей над нами.
Максимум возрастающей и убывающей функций имеет форму «галочки»: сначала падает, потом растёт. Минимум — в точке, где догоняет . Её ищем бинпоиском по ответу: находим первое , где .
from functools import lru_cache def egg_drop_bs(k: int, n: int) -> int: @lru_cache(maxsize=None) def solve(e: int, f: int) -> int: if f == 0: return 0 if e == 1: return f lo, hi = 1, f while lo < hi: mid = (lo + hi) // 2 broke = solve(e - 1, mid - 1) # растёт по mid survived = solve(e, f - mid) # убывает по mid if broke < survived: lo = mid + 1 else: hi = mid return 1 + max(solve(e - 1, lo - 1), solve(e, f - lo)) return solve(k, n) print(egg_drop_bs(3, 14)) # 4 print(egg_drop_bs(2, 100)) # 14
Тонкость: в точке lo уже , и максимум равен . На шаг левее , максимум равен . Почему не нужно сравнивать обе точки? Добавление одного этажа увеличивает ответ не больше чем на 1, поэтому — значения целые, а . Значит, lo не хуже соседа. Код выше сверен с наивным ДП на всех , .
Сложность : около вызовов. На Python проходит впритык, рекурсия с lru_cache ещё и съедает память. Работает, но выглядит как латание дыр. Есть способ лучше.
Отдельно существует оптимизация «монотонной точки разреза» в духе Divide & Conquer DP: оптимальный не убывает с ростом , поэтому указатель можно двигать только вперёд и получить . Но переворот состояния проще и быстрее.
Решение 3: переворачиваем состояние
Ключевой трюк задачи. Вместо вопроса
сколько бросков нужно, чтобы проверить этажей с яйцами?
задаём обратный:
сколько этажей можно гарантированно проверить, если есть бросков и яиц?
Обозначим это . Ответ на исходную задачу — минимальное , при котором .
Вывод перехода
Делаем первый бросок с некоторого этажа. Оптимальную высоту выбирать не нужно — она вытекает сама:
- Если яйцо разбилось, остаются бросков и яиц. Значит, под этажом броска должно быть не больше этажей — ровно столько мы ещё способны проверить.
- Если уцелело, остаются бросков и те же яиц: над этажом броска можно оставить этажей.
- Плюс сам этаж, с которого бросили.
Базы: , .
Заметьте, что исчезли и минимум, и максимум: этаж броска выбирается однозначно — от низа текущего диапазона. Отсюда и выигрыш в сложности.
Таблица
Строки — броски , столбцы — яйца :
| 1 | 1 | 1 | 1 | 1 |
| 2 | 2 | 3 | 3 | 3 |
| 3 | 3 | 6 | 7 | 7 |
| 4 | 4 | 10 | 14 | 15 |
| 5 | 5 | 15 | 25 | 30 |
Сверяем с примерами: — двумя яйцами за 3 броска покрываем 6 этажей; . При столбцы перестают расти: , и это ровно бинарный поиск — яиц хватает, чтобы ни разу не экономить.
Код
Строку считаем из строки , поэтому хватает одномерного массива. Идём по яйцам справа налево, чтобы dp[e - 1] ещё хранило значение прошлого шага — тот же приём, что в рюкзаке.
def super_egg_drop(k: int, n: int) -> int: # dp[e] — сколько этажей покрывают e яиц за m бросков dp = [0] * (k + 1) m = 0 while dp[k] < n: m += 1 for e in range(k, 0, -1): # справа налево: dp[e-1] ещё «старый» dp[e] = dp[e - 1] + dp[e] + 1 return m print(super_egg_drop(1, 2)) # 2 print(super_egg_drop(2, 6)) # 3 print(super_egg_drop(3, 14)) # 4 print(super_egg_drop(2, 100)) # 14 print(super_egg_drop(100, 10**4)) # 14
То же на JavaScript:
function superEggDrop(k, n) { const dp = new Array(k + 1).fill(0) let m = 0 while (dp[k] < n) { m++ for (let e = k; e >= 1; e--) dp[e] = dp[e - 1] + dp[e] + 1 } return m } console.log(superEggDrop(2, 100)) // 14 console.log(superEggDrop(3, 14)) // 4
Сложность
Внешний цикл делает итераций, где — сам ответ, внутренний — . Итого времени и памяти. В худшем случае () , но тогда и внутренний цикл из одной итерации. При ответ около . Для 100 яиц и этажей — 14 итераций по 100 шагов. Против у наивного ДП.
Решение 4: формула через биномы
У перехода есть замкнутая форма:
Проверка индукцией опирается на тождество Паскаля : сумма даёт (слагаемое — это ), а — ровно .
Есть и комбинаторная интерпретация: каждый сценарий испытаний — это последовательность из исходов «разбилось/уцелело», где разбиений не больше . Сценарий с хотя бы одним разбиением однозначно задаёт найденный этаж. Подробнее о биномах — в статье про комбинаторику.
Раз монотонно растёт по , ищем минимальное бинпоиском:
from math import comb def floors_covered(m: int, k: int) -> int: return sum(comb(m, i) for i in range(1, k + 1)) def super_egg_drop_binom(k: int, n: int) -> int: lo, hi = 1, n while lo < hi: mid = (lo + hi) // 2 if floors_covered(mid, k) >= n: hi = mid else: lo = mid + 1 return lo print(super_egg_drop_binom(2, 100)) # 14 print(super_egg_drop_binom(3, 10**9)) # 1818
Бинпоиск делает шагов, каждый считает сумму из биномов. В Python comb работает с большими числами, так что в оценке спрятана длинная арифметика; на C++ или Java надо обрывать сумму, как только она превысила , иначе будет переполнение. На практике решение 3 короче и не хуже.
Разбор: 2 яйца и 100 этажей
Устная версия задачи. Из формулы . Нужно , наименьшее такое ().
Стратегия получается из перехода: первый бросок с этажа .
- Разбилось — осталось одно яйцо, им идём с 1-го по 13-й: максимум бросков.
- Уцелело — следующий бросок на 13 этажей выше, с 27-го. Если разбилось, проверяем 15–26 (12 бросков), итого .
- Дальше шаг уменьшается на единицу: 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100.
Идея «уменьшающегося шага»: каждый успешный бросок тратит одну попытку из бюджета, поэтому «хвост» линейного перебора вторым яйцом должен становиться на единицу короче. Шаг постоянной длины даёт худший случай — хуже на 5 бросков. Это частый неправильный ответ на устном собеседовании.
Восстановление стратегии в коде
Число бросков — половина ответа. На follow-up часто просят: «а с каких этажей бросать?». Переворот состояния отвечает и на это. Пусть осталось бросков и яиц, а лежит в диапазоне этажей от low до high. Бросаем с этажа low + f(m - 1, e - 1): под ним ровно столько этажей, сколько мы сможем проверить, если яйцо разобьётся.
from math import comb def covered(m: int, k: int) -> int: return sum(comb(m, i) for i in range(1, k + 1)) def play(k: int, n: int, secret: int) -> list[int]: """Симулирует оптимальную стратегию, возвращает этажи бросков. secret — искомый F: яйцо бьётся с этажей выше secret. """ m = 0 while covered(m, k) < n: m += 1 low, high = 1, n # F лежит в [low - 1, high] drops = [] while low <= high: floor = min(low + covered(m - 1, k - 1), high) drops.append(floor) m -= 1 if floor > secret: # разбилось k -= 1 high = floor - 1 else: # уцелело low = floor + 1 return drops print(play(2, 100, 0)) # [14, 1] print(play(3, 14, 5)) # [7, 3, 5, 6]
Для , , функция выдаёт [14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 96, 97, 98] — ровно 14 бросков: после разбитого на 99-м яйца остаётся линейно проверить 96–98. Мы прогнали симуляцию для всех , и каждого : бросков никогда не больше ответа, разбитых яиц — не больше .
min(..., high) нужен, когда этажей меньше, чем способен покрыть остаток бюджета: бросать выше крыши бессмысленно.
Почему лучше нельзя
Переворот выглядит как фокус, поэтому интервьюер может спросить, почему — это именно максимум, а не просто «какая-то стратегия». Аргумент короткий.
Любая стратегия с бюджетом бросков и яиц делает первый бросок с какого-то этажа . Если яйцо разбилось, дальше это стратегия с бросками и яйцами, и она обязана различить все этажей ниже — значит, по индукции . Если уцелело — стратегия с бросками и яйцами различает этажи выше: их не больше . Складываем: всего этажей не больше . А конструкция из предыдущего раздела показывает, что этот предел достижим.
Есть и вторая, «информационная» оценка. Исход игры — строка из символов «бьётся/не бьётся» (недоигранные броски дополним «не бьётся»), в которой не больше разбиений. Таких строк . Разных ответов всего , и каждому нужна своя строка, поэтому . Отсюда и биномы.
Типичные ошибки
Обход яиц слева направо в одномерном массиве. Тогда dp[e - 1] уже обновлено на текущем шаге, и этажи считаются дважды:
for e in range(1, k + 1): # ОШИБКА: нужно справа налево dp[e] = dp[e - 1] + dp[e] + 1
С таким циклом для получается 13 вместо 14.
Путаница «этажей» и «границ». может быть от 0 до — это вариант, но этажей для проверки ровно . Отсюда и база , и условие dp[k] < n, а не <= n.
Минимум вместо максимума по исходам. Мы не управляем тем, разобьётся ли яйцо, — это худший случай, значит max. Минимум берётся только по нашему выбору этажа.
Попытка «просто бинпоиска». Работает лишь при . На собеседовании это стоит проговорить как наблюдение, а не как решение.
Неверное направление в бинпоиске по точке броска. Если перепутать, какая из функций растёт, а какая убывает, поиск уедет в край диапазона и ответ получится завышенным. Проверяйте на маленьких против наивного ДП.
Как это спрашивают на собеседованиях
- Устно, 2 яйца и 100 этажей. Ждут 14 и объяснения уменьшающегося шага. Хорошо — сразу вывести .
- Код, общий случай. Нормальный путь: проговорить ДП , показать монотонность и бинпоиск, затем предложить переворот. Если сразу пишете решение 3 — обязательно объясните, откуда переход, иначе это выглядит как заученный трюк.
- Follow-up: «восстановите стратегию» (этаж броска от низа диапазона), «что если » (биномы с отсечкой и бинпоиск по ), «сколько этажей покроют 3 яйца за 10 бросков» ().
Сам приём «поменять местами ответ и параметр» встречается далеко за пределами яиц: когда ДП по «минимальному числу шагов» тяжёлое, попробуйте считать «максимум, достижимый за шагов». Похожий взгляд работает в Jump Game и в задачах, решаемых бинпоиском по ответу.