meskeIA

Simulador de Programación Dinámica

Rellena la tabla de subproblemas paso a paso y observa de qué celdas depende cada valor. Tres clásicos editables: la mochila 0/1, la subsecuencia común más larga y Fibonacci.

© 2026 meskeIA© 2026

Problema

Datos de entrada

#1
#2
#3
#4

Tabla de programación dinámica

Objetos \ Capacidad012345678
∅000000000
#1 (p2/v3)?
#2 (p3/v4)
#3 (p4/v5)
#4 (p5/v6)
Celda [#1 (p2/v3), 0]: Objeto 1 (peso 2): no cabe en capacidad 0 → se hereda 0 de arriba.
Celda 0 de 36
450 ms

Guía de Programación Dinámica

Memoización, tabulación y los problemas clásicos

Recursión ingenua vs Programación dinámica

AspectoRecursión ingenuaProgramación dinámica
Subproblemas repetidosSe recalculan una y otra vezSe calculan una sola vez y se guardan
Coste (Fibonacci)O(2ⁿ) exponencialO(n) lineal
MemoriaSolo la pila de llamadasTabla de subproblemas
EnfoqueArriba abajo naturalMemoización (top-down) o tabulación (bottom-up)
RiesgoTiempo inviableHay que identificar el estado correcto
Cuándo usarlaSin solapamiento de subproblemasSubestructura óptima + subproblemas solapados

Casos de Uso Reales

Control de versiones (diff)
git diff y las herramientas de comparación de archivos usan la subsecuencia común más larga (o la distancia de edición) para mostrar qué líneas se han añadido o borrado.
Tip: la LCS es la base del algoritmo de diff de Myers.
Bioinformática
El alineamiento de secuencias de ADN o proteínas (Needleman-Wunsch, Smith-Waterman) es programación dinámica sobre una tabla, muy parecida a la de la LCS.
Tip: comparar genomas sería inviable sin DP.
Optimización de recursos
La mochila modela decisiones de presupuesto, selección de inversiones o asignación de recursos limitados maximizando el beneficio sin pasarse de un tope.
Tip: el cambio de monedas es otro pariente cercano de la mochila.
Autocorrección y búsqueda
La distancia de edición (Levenshtein) mide cuántos cambios separan dos palabras y alimenta el corrector ortográfico y las sugerencias de búsqueda.
Tip: "¿quizás quisiste decir…?" se apoya en DP.

Preguntas Frecuentes

¿Qué son la subestructura óptima y los subproblemas solapados?

Son las dos condiciones para aplicar DP. Subestructura óptima: la solución óptima del problema se construye con soluciones óptimas de sus subproblemas. Subproblemas solapados: los mismos subproblemas aparecen muchas veces. Si solo se cumple la primera pero no la segunda, suele bastar con divide y vencerás.

Fibonacci es el ejemplo perfecto de subproblemas solapados.

¿Por qué la mochila se llama 0/1?

Porque de cada objeto solo puedes tomar 0 unidades (no lo coges) o 1 (lo coges entero): no se pueden partir. Existe también la "mochila fraccionaria", que sí permite partir objetos y se resuelve con un algoritmo voraz, no con DP.

En el simulador, cada celda decide justo eso: coger o no coger.

¿Cómo se reconstruye la solución, no solo su valor?

La tabla da el valor óptimo, pero para saber qué objetos se eligen (o qué LCS resulta) hay que "deshacer" el camino desde la última celda hasta el inicio, mirando de qué celda vino cada valor. El simulador hace ese backtracking y te muestra el resultado al completar.

Por eso conviene guardar también de dónde viene cada celda.

¿La programación dinámica siempre usa una tabla 2D?

No. La dimensión de la tabla depende del número de variables del estado. Fibonacci usa una tabla 1D; la mochila y la LCS, una 2D; otros problemas necesitan 3D o más. Muchas veces se puede optimizar la memoria guardando solo las últimas filas.

La mochila se puede resolver con un solo array 1D recorrido al revés.

¿Memoización o tabulación, cuál elijo?

La memoización es más fácil de escribir: partes de la recursión y añades una caché. La tabulación evita la recursión, no desborda la pila y suele permitir optimizar memoria, pero exige pensar el orden de llenado. Para empezar, memoización; para producción con entradas grandes, tabulación.

Este simulador muestra la tabulación: llenamos la tabla en orden.

Cómo Plantear un Problema de DP — Paso a Paso

1
Define el estado

¿Qué variables describen un subproblema? En la mochila, "primeros i objetos con capacidad w".

2
Escribe la recurrencia

Expresa la solución de un estado en función de estados más pequeños. Es el corazón de la DP.

3
Fija los casos base

Sin objetos o capacidad 0 → valor 0; cadena vacía → LCS 0. Son las celdas ya rellenas al inicio.

4
Elige el orden de llenado

Cada celda debe calcularse después de aquellas de las que depende. Aquí, de arriba abajo y de izquierda a derecha.

5
Reconstruye la solución

Recorre la tabla hacia atrás para recuperar las decisiones, no solo el valor óptimo.

Claves Prácticas

Identifica el estado mínimo

Un estado más pequeño = tabla más pequeña y solución más rápida. No añadas variables de más.

De recursión a DP

Escribe primero la recursión; si ves subproblemas repetidos, añade memoización casi sin cambiarla.

Optimiza la memoria

Si una celda solo depende de la fila anterior, guarda dos filas en vez de toda la tabla.

Guarda el origen

Si necesitas la solución y no solo su coste, anota de dónde viene cada celda.

Comprueba los límites

Los casos base y los índices fuera de rango son la fuente número uno de errores en DP.

Verifica con casos pequeños

Rellena a mano una tabla 3×3 y compárala con tu código antes de escalar.

Errores frecuentes en programación dinámica
  • Definir un estado incompleto que no captura toda la información del subproblema.
  • Equivocarse en los casos base (la fila o columna inicial).
  • Rellenar la tabla en un orden en el que una celda usa otra aún sin calcular.
  • Confundir la mochila 0/1 (DP) con la fraccionaria (voraz).
  • Quedarse solo con el valor óptimo y no saber reconstruir la solución.
  • Aplicar DP donde no hay subproblemas solapados (sería gastar memoria sin ganancia).

Apps relacionadas