Я начал вести блоги, чтобы помочь таким людям, как я, которые думают, почему это происходит именно так. Этот блог также следует тому же девизу, но пока он следует задаче динамического программирования.

Постановка задачи :

Учитывая N этажей и K яиц, какое минимальное количество попыток требуется, чтобы определить, на каком этаже разобьется яйцо?

Чтобы решить эту проблему, необходимы некоторые допущения -
1. вы можете использовать целое яйцо для следующей попытки
2. вам нужно выбросить разбитое яйцо
3. вам нужно учитывать это яйцо может разбиться с первого этажа или яйцо может не разбиться даже с N-го этажа
4. нужно учитывать, что все яйца будут иметь одинаковую прочность
5. Если яйцо не разобьется на X этаже, оно выиграло не ломаться с 1 по Х-1 этажи

Теперь перейдем к разделу «Как сделать» :

Допустим, у вас есть 1 яйцо и 0 этажей -› здесь вы можете найти количество попыток как 0.
Допустим, у вас есть 1 яйцо и 5 этажей-› здесь у вас есть количество попыток как X-й этаж, так как у вас есть только одно яйцо, которое вам нужно пройти на каждый этаж и проверить, пока ваше яйцо не сломается.
Допустим, у вас есть 0 яиц и N этажей-› довольно просто, правильно, 0так как вам нечего делать

Достаточно начальных условий, теперь давайте погрузимся в ядро:
Подход заключается в том, чтобы найти минимальное количество попыток, необходимых для того, чтобы сказать, на каком этаже может разбиться яйцо, вам нужно рассчитать количество попыток может потребоваться для k яиц с каждого этажа.

аналогия: для каждого этажа у вас есть два простых случая -
1. Яйцо может разбиться - тогда у вас будет (X-1 этажей и k-1 яиц) для раздачи
2. Яйцо не может перерыв - тогда у вас будет (NX этажей и k яиц) для решения

Таким образом, искомое уравнение будет
minAttempts( N , K) = 1 + min( max( minAttempts(X-1, K-1), minAttempts(N-X, k)
для X = от 1 до N

мы добавляем плюс один, чтобы учесть текущую попытку, и min, чтобы получить минимальное количество попыток при попытке с каждого отдельного этажа, и max, чтобы учесть сценарий, в котором яйцо не разобьется, иначе мы можем в конечном итоге рассматривать только сценарии разбивания яйца.

поэтому приведенное выше уравнение, если оно реализовано в рекурсии, выглядит следующим образом

if(eggs == 1){             
   return floors;
 }
if(floors == 0){
    return 0; 
 } 
int min = INT_MAX;
for(int i=1; i <= floors; i++){      
    int val = 1 + Math.max(calculateRecursive(eggs-1, i-1),calculateRecursive(eggs, floors-i));
    if(val < min){
        min = val; 
     }  
   } 
 return min;

Но вы можете наблюдать много избыточных вызовов, если вы отлаживаете строку за строкой, по этой причине вы можете вместо этого выбрать решение для динамического программирования, где вы можете сохранить вычисленные значения в буфере и использовать их вместо повторного вычисления.

Пройдемся по решению DP:
возьмем буфер — T[яйца + 1][этажи + 1]
Дополнительный буфер нужен для случая с нулевыми этажами и нулевыми яйцами

Теперь с одним яйцом количество попыток, необходимых для определения того, разобьется яйцо или нет, будет количеством этажей, поскольку вам нужно спускаться на каждый этаж и проверять, пока яйцо не разобьется. Таким образом, мы можем изначально заполнить буфер таким образом.

for f = 0 to number_of_floors:
   T[1][f] = f

Теперь об оставшихся яйцах:
Как обсуждалось выше, идите на каждый этаж и узнайте количество попыток, необходимых для прорыва этого этажа, и возьмите его минимум.

attempts_through_each_floor = 0
for egg = 2 to number_of_eggs:
  for floor = 1 to number_of_floors:
    T[egg][floor] = INT_MAX
    for k = 1 to floor:
      attempts_through_each_floor = 1 + max(T[egg-1][floor-1], T[egg][number_of_floors - k])
     if T[egg][floor] < attempts_through_each_floor:
       T[egg][floor] = attempts_through_each_floor
#if you are not using java then initialize matrix with zeroes

Таким образом, число в последнем блоке матрицы дает вам желаемое решение. Надеюсь, это поможет вам понять проблему