Dynamic Programming
Memoization, recursion & DP — breaking problems into subproblems
Dynamic programming (DP) solves a hard problem by breaking it into overlapping subproblems and reusing their answers instead of recomputing them.
When does DP apply?
Two properties make a problem a DP candidate: optimal substructure (the best overall answer is built from best sub-answers) and overlapping subproblems (the same sub-answer is needed many times). The Fibonacci sequence is the textbook example — naive recursion recomputes the same values exponentially, while caching them makes it linear.
Top-down vs bottom-up
Memoization (top-down) keeps the natural recursion but caches each result the first time it is computed. Tabulation (bottom-up) fills a table from the smallest subproblems upward, often saving stack space. Both turn exponential work into polynomial work.
Recursion & backtracking
Classic teaching examples — the knapsack problem, the Tower of Hanoi and the N-Queens puzzle — show how recursion, memoization and backtracking relate. Step through them below to watch the recursion tree collapse once results are cached.
Try it interactively
Visualizador de la Mochila 0/1
Programación dinámica (dynamic programming) para el problema de la mochila 0/1 en forma de animación — rellena la tabla DP celda por celda, resaltando las celdas de las que depende cada una, con controles paso a paso. Se ejecuta directamente en el navegador.
Abrir herramientaVisualizador de la secuencia de Fibonacci
La secuencia de Fibonacci ilustrada de forma dinámica — cada término es la suma de los dos anteriores, construida paso a paso con controles interactivos. Se ejecuta directamente en el navegador.
Abrir herramientaSimulador de la Torre de Hanói
Herramienta que simula la solución recursiva de la Torre de Hanói — mueve los discos en el número mínimo de pasos 2ⁿ−1, con control paso a paso. Se ejecuta directamente en el navegador.
Abrir herramientaSimulador de N-Queens
Simulación animada del algoritmo de backtracking (vuelta atrás) para el problema de las N reinas en un tablero de ajedrez — prueba, coloca reinas, detecta conflictos y retrocede con controles paso a paso. Se ejecuta directamente en el navegador.
Abrir herramientaPreguntas frecuentes
¿Qué es el problema de las N reinas?
Consiste en colocar n reinas en un tablero de n×n de forma que ninguna pueda atacar a otra: sin compartir fila, sin compartir columna y sin compartir diagonal.
¿Cómo resuelve este problema el backtracking?
Las reinas se colocan columna por columna. En cada columna se prueba cada fila; si la posición es segura, se avanza de forma recursiva a la siguiente columna; si ninguna fila es segura, el algoritmo retrocede y prueba otra fila en la columna anterior.
¿Cuál es la complejidad temporal del algoritmo?
En el peor caso es aproximadamente O(n!), pero la poda de las posiciones en conflicto permite encontrar una solución mucho más rápido en la práctica.
¿Para qué valores de n existe solución?
Existe solución para todo n excepto 2 y 3. El clásico problema de las 8 reinas tiene 92 soluciones distintas.