Задача о падающих яйцах (Super Egg Drop): от O(k·n²) до O(k log n)

Разбор задачи о яйцах и этажах: ДП O(k·n²), бинпоиск по точке броска, переворот состояния dp[m][k] и формула через биномиальные коэффициенты. Код на Python и JavaScript.

10 мин чтенияалгоритмы · динамическое программирование · бинарный поиск · python

Коротко

ПодходВремяПамятьКогда годится
ДП «яйца × этажи», перебор броскаO(k⋅n2)O(k \cdot n^2)O(kn)O(k n)n≤500n \le 500, объяснить идею
То же + бинпоиск по точке броскаO(k⋅nlog⁡n)O(k \cdot n \log n)O(kn)O(k n)проходит LeetCode, но громоздко
Переворот: dp[m][k] — этажиO(k⋅m)O(k \cdot m), m≤nm \le nO(k)O(k)основное решение на собеседовании
Сумма биномов + бинпоиск по mmO(klog⁡n)O(k \log n)O(1)O(1)красивый финал, follow-up
  • Главная мысль: вместо «сколько бросков нужно на nn этажей» спрашиваем «сколько этажей можно проверить за mm бросков».
  • Переход после переворота: f(m,k)=f(m−1,k−1)+f(m−1,k)+1f(m, k) = f(m-1, k-1) + f(m-1, k) + 1.
  • Ответ для 2 яиц и 100 этажей — 14 бросков, первый бросок с 14-го этажа.

Постановка

У вас kk одинаковых яиц и здание из nn этажей. Существует неизвестный этаж FF (0≤F≤n0 \le F \le n): яйцо, брошенное с этажа выше FF, разбивается, а с этажа FF и ниже — остаётся целым. Целое яйцо можно бросать снова, разбитое — нет.

Нужно найти минимальное число бросков, которое гарантированно (в худшем случае) определяет FF.

Это LeetCode 887 «Super Egg Drop» (Hard), ограничения 1≤k≤1001 \le k \le 100, 1≤n≤1041 \le n \le 10^4. Двухъяичная версия (LeetCode 1884, «Egg Drop With 2 Eggs and N Floors») — классическая головоломка, которую любят спрашивать устно.

Примеры:

  • k=1,n=2k = 1, n = 2 → 2. С одним яйцом рисковать нельзя: бросаем с 1-го, потом со 2-го.
  • k=2,n=6k = 2, n = 6 → 3.
  • k=3,n=14k = 3, n = 14 → 4.
  • k=2,n=100k = 2, n = 100 → 14.

Интуиция: почему не бинпоиск

Первая мысль — обычный бинарный поиск: бросить с 50-го, потом с 25-го или 75-го и так далее. С бесконечным числом яиц это и есть ответ: ⌈log⁡2(n+1)⌉\lceil \log_2(n+1) \rceil бросков. Но яиц мало. Если с двумя яйцами бросить с 50-го и разбить, второе яйцо придётся вести с 1-го этажа вверх по одному — до 49 бросков в худшем случае.

С одним яйцом выбора нет вообще: только линейный перебор, nn бросков. Значит, ответ живёт между log⁡2n\log_2 n и nn, и всё определяется балансом: насколько рискованно бросать «высоко», если разбитое яйцо отнимает инструмент.

Решение 1: ДП «яйца × этажи» за O(k·n²)

Пусть dp[e][f]dp[e][f] — минимум бросков, чтобы гарантированно найти FF при ee яйцах и ff «подозрительных» этажах. Абсолютная высота не важна: важно лишь, сколько этажей осталось проверить.

Бросаем с этажа xx (1≤x≤f1 \le x \le f). Два исхода:

  • Разбилось. Ответ ниже xx: осталось e−1e - 1 яиц и x−1x - 1 этажей.
  • Уцелело. Ответ выше: ee яиц и f−xf - x этажей.

Мы не знаем, какой исход выпадет, поэтому готовимся к худшему и берём максимум. А этаж xx выбираем сами — берём минимум:

dp[e][f]=1+min⁡1≤x≤fmax⁡(dp[e−1][x−1], dp[e][f−x])dp[e][f] = 1 + \min_{1 \le x \le f} \max\big(dp[e-1][x-1],\ dp[e][f-x]\big)

Базы: dp[e][0]=0dp[e][0] = 0 (проверять нечего), dp[1][f]=fdp[1][f] = f (одно яйцо — перебор снизу).

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

Состояний k⋅nk \cdot n, на каждое — перебор nn точек броска: O(k⋅n2)O(k \cdot n^2). Для k=100k = 100, n=104n = 10^4 это 101010^{10} операций — не пройдёт. Но с этого решения стоит начинать на собеседовании: оно честно выводится из постановки и показывает, что вы видите «минимакс» — мы минимизируем по своему выбору и максимизируем по выбору противника (природы).

Пример: 2 яйца, 6 этажей

Посчитаем dp[2][6]dp[2][6] вручную. Строка для одного яйца тривиальна: dp[1][f]=fdp[1][f] = f. Строка для двух яиц до f=5f = 5 уже готова: dp[2][⋅]=[0,1,2,2,3,3]dp[2][\cdot] = [0, 1, 2, 2, 3, 3]. Перебираем точку первого броска:

xxразбилось: dp[1][x−1]dp[1][x-1]уцелело: dp[2][6−x]dp[2][6-x]1+max⁡1 + \max
1034
2134
3223
4324
5415
6506

Минимум — 3, при броске с 3-го этажа. Видно и форму «галочки»: левый столбец растёт, средний убывает, а лучший xx — там, где они встречаются. Это наблюдение и даст следующую оптимизацию.

Если динамика пока даётся тяжело, сначала разберите ДП для начинающих и задачу о размене монет — там та же логика «перебираем последний шаг».

Решение 2: бинпоиск по точке броска, O(k·n log n)

Посмотрим на два слагаемых под максимумом как на функции от xx при фиксированных ee и ff:

  • A(x)=dp[e−1][x−1]A(x) = dp[e-1][x-1] — не убывает по xx: чем выше бросаем, тем больше этажей под нами, тем больше работы, если разобьётся.
  • B(x)=dp[e][f−x]B(x) = dp[e][f-x] — не возрастает по xx: чем выше бросаем, тем меньше этажей над нами.

Максимум возрастающей и убывающей функций имеет форму «галочки»: сначала падает, потом растёт. Минимум — в точке, где AA догоняет BB. Её ищем бинпоиском по ответу: находим первое xx, где A(x)≥B(x)A(x) \ge B(x).

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 уже A≥BA \ge B, и максимум равен A(lo)A(lo). На шаг левее A<BA < B, максимум равен B(lo−1)B(lo-1). Почему не нужно сравнивать обе точки? Добавление одного этажа увеличивает ответ не больше чем на 1, поэтому A(lo)≤A(lo−1)+1≤B(lo−1)A(lo) \le A(lo-1) + 1 \le B(lo-1) — значения целые, а A(lo−1)<B(lo−1)A(lo-1) < B(lo-1). Значит, lo не хуже соседа. Код выше сверен с наивным ДП на всех k≤5k \le 5, n<120n < 120.

Сложность O(k⋅nlog⁡n)O(k \cdot n \log n): около 104⋅100⋅14≈1.4⋅10710^4 \cdot 100 \cdot 14 \approx 1.4 \cdot 10^7 вызовов. На Python проходит впритык, рекурсия с lru_cache ещё и съедает память. Работает, но выглядит как латание дыр. Есть способ лучше.

Отдельно существует оптимизация «монотонной точки разреза» в духе Divide & Conquer DP: оптимальный xx не убывает с ростом ff, поэтому указатель можно двигать только вперёд и получить O(k⋅n)O(k \cdot n). Но переворот состояния проще и быстрее.

Решение 3: переворачиваем состояние

Ключевой трюк задачи. Вместо вопроса

сколько бросков нужно, чтобы проверить nn этажей с kk яйцами?

задаём обратный:

сколько этажей можно гарантированно проверить, если есть mm бросков и kk яиц?

Обозначим это f(m,k)f(m, k). Ответ на исходную задачу — минимальное mm, при котором f(m,k)≥nf(m, k) \ge n.

Вывод перехода

Делаем первый бросок с некоторого этажа. Оптимальную высоту выбирать не нужно — она вытекает сама:

  • Если яйцо разбилось, остаются m−1m - 1 бросков и k−1k - 1 яиц. Значит, под этажом броска должно быть не больше f(m−1,k−1)f(m-1, k-1) этажей — ровно столько мы ещё способны проверить.
  • Если уцелело, остаются m−1m - 1 бросков и те же kk яиц: над этажом броска можно оставить f(m−1,k)f(m-1, k) этажей.
  • Плюс сам этаж, с которого бросили.
f(m,k)=f(m−1,k−1)+f(m−1,k)+1f(m, k) = f(m-1, k-1) + f(m-1, k) + 1

Базы: f(0,k)=0f(0, k) = 0, f(m,0)=0f(m, 0) = 0.

Заметьте, что исчезли и минимум, и максимум: этаж броска выбирается однозначно — f(m−1,k−1)+1f(m-1, k-1) + 1 от низа текущего диапазона. Отсюда и выигрыш в сложности.

Таблица

Строки — броски mm, столбцы — яйца kk:

mmk=1k=1k=2k=2k=3k=3k=4k=4
11111
22333
33677
44101415
55152530

Сверяем с примерами: f(3,2)=6f(3, 2) = 6 — двумя яйцами за 3 броска покрываем 6 этажей; f(4,3)=14f(4, 3) = 14. При k≥mk \ge m столбцы перестают расти: f(m,k)=2m−1f(m, k) = 2^m - 1, и это ровно бинарный поиск — яиц хватает, чтобы ни разу не экономить.

Код

Строку mm считаем из строки m−1m - 1, поэтому хватает одномерного массива. Идём по яйцам справа налево, чтобы 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

Сложность

Внешний цикл делает mm итераций, где mm — сам ответ, внутренний — kk. Итого O(k⋅m)O(k \cdot m) времени и O(k)O(k) памяти. В худшем случае (k=1k = 1) m=nm = n, но тогда и внутренний цикл из одной итерации. При k≥log⁡2nk \ge \log_2 n ответ около log⁡2n\log_2 n. Для 100 яиц и 10410^4 этажей — 14 итераций по 100 шагов. Против 101010^{10} у наивного ДП.

Решение 4: формула через биномы

У перехода f(m,k)=f(m−1,k−1)+f(m−1,k)+1f(m, k) = f(m-1, k-1) + f(m-1, k) + 1 есть замкнутая форма:

f(m,k)=∑i=1k(mi)f(m, k) = \sum_{i=1}^{k} \binom{m}{i}

Проверка индукцией опирается на тождество Паскаля (mi)=(m−1i−1)+(m−1i)\binom{m}{i} = \binom{m-1}{i-1} + \binom{m-1}{i}: сумма ∑i=1k(m−1i−1)\sum_{i=1}^{k} \binom{m-1}{i-1} даёт 1+f(m−1,k−1)1 + f(m-1, k-1) (слагаемое i=1i = 1 — это (m−10)=1\binom{m-1}{0} = 1), а ∑i=1k(m−1i)\sum_{i=1}^{k} \binom{m-1}{i} — ровно f(m−1,k)f(m-1, k).

Есть и комбинаторная интерпретация: каждый сценарий испытаний — это последовательность из mm исходов «разбилось/уцелело», где разбиений не больше kk. Сценарий с хотя бы одним разбиением однозначно задаёт найденный этаж. Подробнее о биномах — в статье про комбинаторику.

Раз f(m,k)f(m, k) монотонно растёт по mm, ищем минимальное mm бинпоиском:

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

Бинпоиск делает O(log⁡n)O(\log n) шагов, каждый считает сумму из kk биномов. В Python comb работает с большими числами, так что в оценке O(klog⁡n)O(k \log n) спрятана длинная арифметика; на C++ или Java надо обрывать сумму, как только она превысила nn, иначе будет переполнение. На практике решение 3 короче и не хуже.

Разбор: 2 яйца и 100 этажей

Устная версия задачи. Из формулы f(m,2)=m+(m2)=m(m+1)2f(m, 2) = m + \binom{m}{2} = \frac{m(m+1)}{2}. Нужно m(m+1)2≥100\frac{m(m+1)}{2} \ge 100, наименьшее такое m=14m = 14 (14⋅15/2=10514 \cdot 15 / 2 = 105).

Стратегия получается из перехода: первый бросок с этажа f(13,1)+1=14f(13, 1) + 1 = 14.

  • Разбилось — осталось одно яйцо, им идём с 1-го по 13-й: максимум 1+13=141 + 13 = 14 бросков.
  • Уцелело — следующий бросок на 13 этажей выше, с 27-го. Если разбилось, проверяем 15–26 (12 бросков), итого 2+12=142 + 12 = 14.
  • Дальше шаг уменьшается на единицу: 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100.

Идея «уменьшающегося шага»: каждый успешный бросок тратит одну попытку из бюджета, поэтому «хвост» линейного перебора вторым яйцом должен становиться на единицу короче. Шаг постоянной длины n=10\sqrt{n} = 10 даёт худший случай 10+9=1910 + 9 = 19 — хуже на 5 бросков. Это частый неправильный ответ на устном собеседовании.

Восстановление стратегии в коде

Число бросков — половина ответа. На follow-up часто просят: «а с каких этажей бросать?». Переворот состояния отвечает и на это. Пусть осталось mm бросков и ee яиц, а FF лежит в диапазоне этажей от 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]

Для k=2k = 2, n=100n = 100, F=98F = 98 функция выдаёт [14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 96, 97, 98] — ровно 14 бросков: после разбитого на 99-м яйца остаётся линейно проверить 96–98. Мы прогнали симуляцию для всех k≤4k \le 4, n<80n < 80 и каждого FF: бросков никогда не больше ответа, разбитых яиц — не больше kk.

min(..., high) нужен, когда этажей меньше, чем способен покрыть остаток бюджета: бросать выше крыши бессмысленно.

Почему лучше нельзя

Переворот выглядит как фокус, поэтому интервьюер может спросить, почему f(m,k)f(m, k) — это именно максимум, а не просто «какая-то стратегия». Аргумент короткий.

Любая стратегия с бюджетом mm бросков и kk яиц делает первый бросок с какого-то этажа xx. Если яйцо разбилось, дальше это стратегия с m−1m - 1 бросками и k−1k - 1 яйцами, и она обязана различить все xx этажей ниже — значит, по индукции x−1≤f(m−1,k−1)x - 1 \le f(m-1, k-1). Если уцелело — стратегия с m−1m - 1 бросками и kk яйцами различает этажи выше: их не больше f(m−1,k)f(m-1, k). Складываем: всего этажей не больше f(m−1,k−1)+1+f(m−1,k)=f(m,k)f(m-1, k-1) + 1 + f(m-1, k) = f(m, k). А конструкция из предыдущего раздела показывает, что этот предел достижим.

Есть и вторая, «информационная» оценка. Исход игры — строка из mm символов «бьётся/не бьётся» (недоигранные броски дополним «не бьётся»), в которой не больше kk разбиений. Таких строк ∑i=0k(mi)=f(m,k)+1\sum_{i=0}^{k} \binom{m}{i} = f(m, k) + 1. Разных ответов FF всего n+1n + 1, и каждому нужна своя строка, поэтому n+1≤f(m,k)+1n + 1 \le f(m, k) + 1. Отсюда и биномы.

Типичные ошибки

Обход яиц слева направо в одномерном массиве. Тогда dp[e - 1] уже обновлено на текущем шаге, и этажи считаются дважды:

for e in range(1, k + 1): # ОШИБКА: нужно справа налево dp[e] = dp[e - 1] + dp[e] + 1

С таким циклом для k=2,n=100k = 2, n = 100 получается 13 вместо 14.

Путаница «этажей» и «границ». FF может быть от 0 до nn — это n+1n + 1 вариант, но этажей для проверки ровно nn. Отсюда и база dp[e][0]=0dp[e][0] = 0, и условие dp[k] < n, а не <= n.

Минимум вместо максимума по исходам. Мы не управляем тем, разобьётся ли яйцо, — это худший случай, значит max. Минимум берётся только по нашему выбору этажа.

Попытка «просто бинпоиска». Работает лишь при k≥⌈log⁡2(n+1)⌉k \ge \lceil \log_2(n+1) \rceil. На собеседовании это стоит проговорить как наблюдение, а не как решение.

Неверное направление в бинпоиске по точке броска. Если перепутать, какая из функций растёт, а какая убывает, поиск уедет в край диапазона и ответ получится завышенным. Проверяйте на маленьких nn против наивного ДП.

Как это спрашивают на собеседованиях

  • Устно, 2 яйца и 100 этажей. Ждут 14 и объяснения уменьшающегося шага. Хорошо — сразу вывести m(m+1)2≥n\frac{m(m+1)}{2} \ge n.
  • Код, общий случай. Нормальный путь: проговорить ДП O(kn2)O(k n^2), показать монотонность и бинпоиск, затем предложить переворот. Если сразу пишете решение 3 — обязательно объясните, откуда переход, иначе это выглядит как заученный трюк.
  • Follow-up: «восстановите стратегию» (этаж броска =f(m−1,k−1)+1= f(m-1, k-1) + 1 от низа диапазона), «что если n=1018n = 10^{18}» (биномы с отсечкой и бинпоиск по mm), «сколько этажей покроют 3 яйца за 10 бросков» ((101)+(102)+(103)=175\binom{10}{1} + \binom{10}{2} + \binom{10}{3} = 175).

Сам приём «поменять местами ответ и параметр» встречается далеко за пределами яиц: когда ДП по «минимальному числу шагов» тяжёлое, попробуйте считать «максимум, достижимый за mm шагов». Похожий взгляд работает в Jump Game и в задачах, решаемых бинпоиском по ответу.

Потренироваться в спокойной обстановке

Все задачи

Читать дальше

Все статьи