Cargando aplicación...
Preparando tu experiencia meskeIA
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.
| Objetos \ Capacidad | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| ∅ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| #1 (p2/v3) | ? | ||||||||
| #2 (p3/v4) | |||||||||
| #3 (p4/v5) | |||||||||
| #4 (p5/v6) |
Memoización, tabulación y los problemas clásicos
| Aspecto | Recursión ingenua | Programación dinámica |
|---|---|---|
| Subproblemas repetidos | Se recalculan una y otra vez | Se calculan una sola vez y se guardan |
| Coste (Fibonacci) | O(2ⁿ) exponencial | O(n) lineal |
| Memoria | Solo la pila de llamadas | Tabla de subproblemas |
| Enfoque | Arriba abajo natural | Memoización (top-down) o tabulación (bottom-up) |
| Riesgo | Tiempo inviable | Hay que identificar el estado correcto |
| Cuándo usarla | Sin solapamiento de subproblemas | Subestructura óptima + 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.
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.
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.
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.
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.
¿Qué variables describen un subproblema? En la mochila, "primeros i objetos con capacidad w".
Expresa la solución de un estado en función de estados más pequeños. Es el corazón de la DP.
Sin objetos o capacidad 0 → valor 0; cadena vacía → LCS 0. Son las celdas ya rellenas al inicio.
Cada celda debe calcularse después de aquellas de las que depende. Aquí, de arriba abajo y de izquierda a derecha.
Recorre la tabla hacia atrás para recuperar las decisiones, no solo el valor óptimo.
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.
Escribe primero la recursión; si ves subproblemas repetidos, añade memoización casi sin cambiarla.
Si una celda solo depende de la fila anterior, guarda dos filas en vez de toda la tabla.
Si necesitas la solución y no solo su coste, anota de dónde viene cada celda.
Los casos base y los índices fuera de rango son la fuente número uno de errores en DP.
Rellena a mano una tabla 3×3 y compárala con tu código antes de escalar.