Saltar al contenido

Top-down vs. bottom-up

Lección 2 de 20 · 5 min

Top-down vs. bottom-up

Paso 1 de 12

Top-down (de arriba hacia abajo) parte del problema completo, fib(4), y solo recursa en lo que de verdad necesita.

La idea

Dos direcciones, una recurrencia. Top-down (de arriba hacia abajo) empieza por el problema completo, hace recursión y guarda en caché lo que encuentra: solo toca los subproblemas que realmente necesita. Bottom-up (de abajo hacia arriba) empieza por los casos base y llena una tabla hacia adelante, así cada dependencia está lista antes de leerse. Top-down sale más fácil de la recursión; bottom-up evita pilas de llamadas profundas.

Ejemplo del mundo real

Repasar para un examen. Top-down es abrir el examen pasado más difícil y consultar algo solo cuando una pregunta lo exige. Bottom-up es estudiar el temario capítulo por capítulo, así nunca te falta nada al llegar al examen, aunque también estudias páginas que el examen nunca pregunta.

El código

Te toca

Ordena los pasos.

  1. Llena las celdas restantes en orden de dependencias
  2. Decide qué va a significar una sola celda de la tabla
  3. Lee la última celda como la respuesta
  4. Escribe directamente las celdas de los casos base

Mini quiz

1 / 3

La DP top-down se describe mejor como: