A seguir está uma descrição da instância deste famoso quebra-cabeça envolvendo n = 2 ovos e um edifício com k = 36 andares.
Suponha que desejamos saber quais histórias em um prédio de 36 andares são seguras para derrubar ovos e quais farão com que os ovos se quebrem na aterrissagem. Fazemos algumas suposições:
... Um ovo que sobrevive a uma queda pode ser usado novamente.
… ..Um ovo quebrado deve ser descartado.
… ..O efeito de uma queda é o mesmo para todos os ovos.
… ..Se um ovo quebrar ao cair, ele quebraria se cair de um andar superior.
... Se um ovo sobreviver a uma queda, ele sobreviverá a uma queda mais curta.
… ..Não está descartado que as janelas do primeiro andar quebrem ovos, nem está descartado que o 36º andar não cause a quebra de um ovo.

Se apenas um ovo estiver disponível e desejamos ter certeza de obter o resultado correto, o experimento pode ser realizado de apenas uma maneira. Solte o ovo da janela do primeiro andar; se sobreviver, jogue-o da janela do segundo andar. Continue subindo até que se quebre. Na pior das hipóteses, esse método pode exigir 36 fezes. Suponha que 2 ovos estejam disponíveis. Qual é o menor número de fezes de ovos que funcionam em todos os casos? 

O problema não é realmente encontrar o piso crítico, mas apenas decidir os pisos de onde os ovos devem ser descartados, de forma que o número total de tentativas seja minimizado.

Fonte: Wiki para Programação Dinâmica

Solução de Programação Dinâmica

<?php
// A Dynamic Programming based PHP
// Program for the Egg Dropping Puzzle
 
/* Function to get minimum number
   of trials needed in worst
   case with n eggs and k floors */
function eggDrop($n, $k)
{
     
    /* A 2D table where entry eggFloor[i][j]
       will represent minimum number of
       trials needed for i eggs and j floors. */
    $eggFloor = array(array());;
     
    // We need one trial for one
    // floor and0 trials for 0 floors
    for ($i = 1; $i <=$n;$i++)
    {
        $eggFloor[$i][1] = 1;
        $eggFloor[$i][0] = 0;
    }
 
    // We always need j trials
    // for one egg and j floors.
    for ($j = 1; $j <= $k; $j++)
        $eggFloor[1][$j] = $j;
 
    // Fill rest of the entries in
    // table using optimal substructure
    // property
    for ($i = 2; $i <= $n; $i++)
    {
        for ($j = 2; $j <= $k; $j++)
        {
            $eggFloor[$i][$j] = 999999;
            for ($x = 1; $x <= $j; $x++)
            {
                $res = 1 + max($eggFloor[$i - 1][$x - 1],
                                 $eggFloor[$i][$j - $x]);
                if ($res < $eggFloor[$i][$j])
                    $eggFloor[$i][$j] = $res;
            }
        }
    }
 
    // eggFloor[n][k] holds the result
    return $eggFloor[$n][$k];
}
 
    // Driver Code
    $n = 2;
    $k = 36;
    echo "Minimum number of trials in worst case with " .$n. " eggs and "
                                    .$k. " floors is " .eggDrop($n, $k) ;
                                     
// This code is contributed by Sam007
?>

O número mínimo de tentativas no pior caso com 2 ovos e 36 andares é 8

Consulte o artigo completo sobre quebra-cabeça de queda de ovo | DP-11 para mais detalhes!