En un comentario del post anterior, Kardo mostraba una solución al problema en 19 intentos:
… Siguiendo este pensamiento, la idea es probar en los pisos múltiplos de N y, en el momento que la lámpara se rompe, probar en los anteriores N-1 pisos para buscar el piso mínimo. De esta forma, si buscamos el mínimo de la función f(100/N+N-1) con 1<N<100, encontramos que ese valor es 19.
Esa es la mejor solución “inteligible” al problema entre las que vi, pero no llega a ser óptima.
El algoritmo
Para buscar la solución óptima, definamos dos funciones: 
Si hay un candidato solo restante no hace falta seguir realizando lanzamientos, por lo que
Por otro lado, si solo nos queda una lámpara no podemos arriesgarnos a que se rompa quedando pisos sin explorar y tendremos que ir probando piso por piso. Por consiguiente tendremos
En los otros casos habrá que efectuar un cierto número de lanzamientos para determinar el piso mínimo. No podemos saber a priori cual será el piso óptimo desde donde realizar el siguiente lanzamiento, pero sabemos que será uno de los
ya que la estrategia óptima elegirá el piso desde donde lanzar de modo de minimizar el costo.
Pero cuando realizamos un lanzamiento desde el piso 
Con esto tenemos definidas casi por completo a las funciones 
que es más simple que separar los casos en que es innecesario buscar.
El algoritmo implementado
La implementación, en este caso en Python, es directa a partir de las definiciones recursivas:
def cost(n, l):
if n in (0, 1):
return 0
elif l == 1:
return n
else:
return min(fixed_try_cost(t, n, l) for t in xrange(0, n))
def fixed_try_cost(t, n, l):
return 1 + max(cost(t, l-1), cost(n - t - 1, l))
Pero si intentamos ejecutar cost(100, 2), observaremos que la ejecución no termina. Esto es debido a que, al igual que en caso del cálculo recursivo de los números de Fibonacci, se recalculan los mismos valores un gran número de veces. Incluso la ejecución de cost(24, 2) demora decenas de segundos.
El algoritmo utilizando programación dinámica
Una forma común para resolver este problema es aplicar la técnica conocida como programación dinámica, consistente esencialmente en almacenar los resultados previamente calculados de modo de no requerir calcularlos nuevamente. Una forma simple de implementar esto en Python es utilizar un diccionario para almacenar el costo correspondiente a cada valor de
costs = {}
def m_fixed_try_cost(t, n, l):
return 1 + max(m_cost(t, l-1), m_cost(n - t - 1, l))
def m_cost(n, l):
if (n, l) in costs:
return costs[(n, l)]
if n in (0, 1):
c = 0
elif l == 1:
c = n
else:
c = min(m_fixed_try_cost(t, n, l) for t in xrange(0, n))
costs[(n, l)] = c
return c
Se observa que las únicas diferencias (aparte del prefijo m_) son la consulta del diccionario al inicio de la función m_cost y el grabado del valor calculado antes de devolverlo.
Si se desea obtener mejor performance, puede utilizarse una tabla normal y llenarla mediante iteración en lugar de recursión. Por ejemplo, la misma función podría implementarse en C del siguiente modo:
#define MAX_N 200
#define MAX_L 200
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
int cost(int n, int l)
{
int costs[MAX_N][MAX_L];
int i, j, k, c;
for (i = 0; i <= n; i++)
costs[i][1] = i;
for (j = 1; j <= l; j++)
costs[0][j] = costs[1][j] = 0;
for (i = 2; i <= n; i++)
{
for (j = 2; j <= l; j++)
{
c = i;
for (k = 0; k < i; k++)
{
c = MIN(c, 1 + MAX(costs[k][j-1],
costs[i-k-1][j]));
}
costs[i][j] = c;
}
}
return costs[n][l];
}
De todos modos, todas las versiones se ejecutan en forma esencialmente instantánea, dando como resultado 
Spin Foam 