Por qué la programación dinámica parece difícil y no lo es
Pocas técnicas de programación generan tanta ansiedad como la programación dinámica. Aparece en casi cualquier proceso de entrevistas técnicas exigente, se esconde detrás de problemas que parecen imposibles y suele explicarse con fórmulas que surgen de la nada. Muchas personas terminan memorizando soluciones de problemas concretos sin entender por qué funcionan, y se bloquean en cuanto el enunciado cambia ligeramente.
La buena noticia es que la programación dinámica no consiste en inventar una solución brillante para cada problema. La inmensa mayoría de los ejercicios que encontrarás encajan en un puñado de patrones que se repiten. Cuando aprendes a reconocer el patrón, la estructura de la solución aparece casi sola: sabes qué representa cada celda de la tabla, de qué celdas anteriores depende y en qué orden rellenarla.
En esta guía recorrerás seis patrones fundamentales con problemas clásicos resueltos en Python, explicando en cada caso cómo se piensa la solución y no solo cuál es. Todos los ejemplos funcionan con Python 3.15, la versión estable más reciente, y con cualquier versión moderna de Python 3. Para cada patrón verás también cómo visualizar la tabla que se construye, porque ver cómo se llena es la forma más rápida de interiorizar la técnica.
Qué es exactamente la programación dinámica
La programación dinámica es una técnica para resolver problemas que se pueden descomponer en subproblemas más pequeños, cuando esos subproblemas se repiten. En lugar de resolver el mismo subproblema una y otra vez, lo resuelves una vez, guardas el resultado y lo reutilizas.
Para que un problema admita programación dinámica debe cumplir dos propiedades.
La primera es la subestructura óptima: la solución óptima del problema completo se puede construir a partir de las soluciones óptimas de sus subproblemas. Por ejemplo, el camino más corto de A a C que pasa por B está formado por el camino más corto de A a B y el más corto de B a C.
La segunda es la superposición de subproblemas: al descomponer el problema, los mismos subproblemas aparecen muchas veces. Si no se repiten, como ocurre al ordenar un arreglo con mergesort, basta con divide y vencerás; no hay nada que reutilizar.
Para resolver cualquier problema de programación dinámica conviene seguir siempre los mismos cuatro pasos:
- Definir el estado: qué significa exactamente
dp[i]odp[i][j]. Este es el paso más importante; una definición precisa hace que lo demás sea casi mecánico. - Encontrar la transición: cómo se calcula un estado a partir de otros más pequeños.
- Fijar los casos base: los estados que conoces sin calcular nada.
- Decidir el orden de cálculo y dónde está la respuesta final.
Los seis patrones de esta guía son, en esencia, seis formas típicas de responder a estos cuatro pasos.
Memoización y tabulación: dos formas de guardar resultados
Hay dos maneras de implementar programación dinámica, y conviene dominar ambas.
Veamos el problema más sencillo posible para compararlas. Tienes una escalera de n peldaños y en cada paso puedes subir uno o dos. ¿De cuántas formas distintas puedes llegar arriba? Para estar en el peldaño n, el último paso fue desde el n - 1 o desde el n - 2, así que el número de formas es la suma de ambos.
La versión recursiva directa es elegante pero catastróficamente lenta, porque recalcula los mismos valores una y otra vez:
def formas_subir_lento(n: int) -> int:
if n <= 1:
return 1
return formas_subir_lento(n - 1) + formas_subir_lento(n - 2)
Para n = 40 hace cientos de millones de llamadas. La memoización, o enfoque de arriba abajo, mantiene la recursión pero guarda cada resultado la primera vez que se calcula. En Python moderno basta con un decorador de la biblioteca estándar:
from functools import cache
@cache
def formas_subir(n: int) -> int:
if n <= 1:
return 1
return formas_subir(n - 1) + formas_subir(n - 2)
print(formas_subir(40))
165580141
El decorador @cache guarda en un diccionario cada combinación de argumentos y su resultado. La complejidad pasa de exponencial a lineal sin cambiar la lógica. Es la forma más rápida de convertir una idea recursiva en una solución eficiente.
La tabulación, o enfoque de abajo arriba, elimina la recursión y rellena una tabla desde los casos base hacia el resultado:
def formas_subir_tabla(n: int) -> int:
if n <= 1:
return 1
dp = [0] * (n + 1)
dp[0] = dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
Si observas la tabla, verás que cada celda solo depende de las dos anteriores. Eso permite una optimización de espacio muy habitual: guardar solo esas dos variables.
def formas_subir_optimo(n: int) -> int:
previo, actual = 1, 1
for _ in range(2, n + 1):
previo, actual = actual, previo + actual
return actual
¿Cuándo usar cada enfoque? La memoización es más natural cuando piensas el problema de forma recursiva y solo se visita una parte de los estados posibles. La tabulación evita el límite de profundidad de recursión de Python, que por defecto ronda las mil llamadas, suele ser más rápida y permite optimizar el espacio. Un flujo de trabajo muy eficaz es escribir primero la versión memoizada para validar la idea y después convertirla en tabla.
Patrón 1: transición constante
En este patrón, cada estado depende de un número fijo de estados anteriores. La escalera es el ejemplo más simple: cada peldaño depende exactamente de los dos anteriores. Cuando reconozcas este patrón, sabrás que la solución será un arreglo unidimensional y, casi siempre, que podrás reducir el espacio a unas pocas variables.
Veamos un problema con algo más de miga. Un repartidor recorre una calle de casas y cada una le ofrece una propina distinta. La regla es que no puede aceptar propinas de dos casas contiguas. ¿Cuál es la máxima cantidad que puede reunir?
El estado se define así: dp[i] es la propina máxima considerando las casas hasta la i. En cada casa hay dos opciones. Si la acepta, no pudo aceptar la anterior, así que obtiene dp[i - 2] + propina[i]. Si la salta, se queda con dp[i - 1]. La transición es el máximo de ambas.
def max_propinas(propinas: list[int]) -> int:
con_actual, sin_actual = 0, 0
for propina in propinas:
con_actual, sin_actual = sin_actual + propina, max(con_actual, sin_actual)
return max(con_actual, sin_actual)
print(max_propinas([4, 11, 3, 6, 9]))
20
Esta versión ya usa la optimización de espacio: con_actual es lo mejor que puede obtener aceptando la casa actual y sin_actual lo mejor saltándola. Si visualizas la tabla para el ejemplo, la evolución es esta:
casa 0 1 2 3 4
propina 4 11 3 6 9
mejor 4 11 11 17 20
La solución óptima acepta las casas 1 y 4, con 11 y 9. Fíjate en que una estrategia voraz, como elegir siempre la propina más alta disponible, puede fallar en otros casos; la programación dinámica explora implícitamente todas las combinaciones sin enumerarlas.
Patrón 2: cuadrículas
Cuando el problema transcurre en una cuadrícula y te mueves en direcciones restringidas, el estado natural es dp[fila][col], y cada celda depende de sus vecinas ya calculadas.
El problema clásico es contar caminos. Un robot está en la esquina superior izquierda de una cuadrícula y solo puede moverse hacia la derecha o hacia abajo. ¿Cuántos caminos distintos hay hasta la esquina inferior derecha?
A una celda solo se puede llegar desde arriba o desde la izquierda, así que dp[f][c] = dp[f - 1][c] + dp[f][c - 1]. Los casos base son la primera fila y la primera columna, a las que solo se llega de una forma.
def contar_caminos(filas: int, columnas: int) -> int:
fila = [1] * columnas
for _ in range(1, filas):
for c in range(1, columnas):
fila[c] += fila[c - 1]
return fila[-1]
print(contar_caminos(3, 4))
10
Aquí aparece otra optimización típica de este patrón: como cada fila solo depende de la anterior, basta con un arreglo de una dimensión que se actualiza en el sitio. Antes de actualizar, fila[c] contiene el valor de la fila de arriba; fila[c - 1] ya contiene el de la izquierda en la fila actual. La tabla completa para una cuadrícula de tres por cuatro sería:
1 1 1 1
1 2 3 4
1 3 6 10
Este patrón admite muchas variantes: cuadrículas con obstáculos, donde la celda bloqueada vale cero; el camino de coste mínimo, donde se cambia la suma por un mínimo más el coste de la celda; o el cuadrado más grande de unos en una matriz binaria. En todas, la pregunta clave es la misma: ¿desde qué celdas puedo llegar a esta?
Patrón 3: dos secuencias
Cuando el problema compara dos cadenas o dos listas, el estado casi siempre es dp[i][j], que representa la respuesta considerando los primeros i elementos de la primera secuencia y los primeros j de la segunda. Este patrón es probablemente el más importante en la práctica, porque está detrás de herramientas que usas a diario.
El primer problema es la subsecuencia común más larga, conocida por sus siglas en inglés, LCS. Una subsecuencia se obtiene eliminando caracteres sin cambiar el orden de los restantes. Dadas dos cadenas, buscamos la longitud de la subsecuencia más larga que comparten.
La transición compara los últimos caracteres de cada prefijo. Si coinciden, forman parte de la subsecuencia común y sumamos uno a la diagonal. Si no coinciden, descartamos el último carácter de una de las dos cadenas y nos quedamos con la mejor opción.
def subsecuencia_comun(a: str, b: str) -> int:
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
print(subsecuencia_comun("ALGORITMO", "LOGARITMO"))
7
La tabla tiene una fila y una columna extra con ceros, que representan los prefijos vacíos. Este truco simplifica los casos base y evita comprobaciones de índices negativos. Observa también la forma de crear la matriz: [[0] * (n + 1) for _ in range(m + 1)]. Escribir [[0] * (n + 1)] * (m + 1) sería un error clásico, porque crearía muchas referencias a la misma fila.
El segundo problema es la distancia de edición, también llamada distancia de Levenshtein: el número mínimo de inserciones, eliminaciones o sustituciones de caracteres para transformar una cadena en otra. Es la base de los correctores ortográficos, de la búsqueda aproximada y de la comparación de secuencias genéticas.
def distancia_edicion(origen: str, destino: str) -> int:
m, n = len(origen), len(destino)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i # borrar todos los caracteres
for j in range(n + 1):
dp[0][j] = j # insertar todos los caracteres
for i in range(1, m + 1):
for j in range(1, n + 1):
if origen[i - 1] == destino[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(
dp[i - 1][j], # eliminar
dp[i][j - 1], # insertar
dp[i - 1][j - 1], # sustituir
)
return dp[m][n]
print(distancia_edicion("gato", "pato"))
print(distancia_edicion("domingo", "dominó"))
1
2
Cada una de las tres celdas vecinas corresponde a una operación: venir desde arriba es eliminar un carácter del origen, venir desde la izquierda es insertar uno del destino y venir en diagonal es sustituir. Esta correspondencia entre direcciones y operaciones es lo que hace tan útil visualizar la tabla: si recorres el camino óptimo hacia atrás desde la esquina inferior derecha, obtienes la lista exacta de cambios, que es justo lo que hace una herramienta de diferencias como diff.
Patrón 4: programación dinámica sobre intervalos
En este patrón, el estado dp[i][j] representa la respuesta para el fragmento de la secuencia que va del índice i al j. La solución de un intervalo se construye a partir de intervalos más pequeños contenidos en él.
El ejemplo clásico es la subsecuencia palindrómica más larga: dada una cadena, buscamos la longitud de la subsecuencia más larga que se lee igual en ambos sentidos.
Si los extremos del intervalo coinciden, ambos forman parte del palíndromo y sumamos dos a la respuesta del interior. Si no coinciden, al menos uno sobra, así que tomamos el mejor resultado descartando el extremo izquierdo o el derecho.
def palindromo_mas_largo(texto: str) -> int:
n = len(texto)
dp = [[0] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
dp[i][i] = 1
for j in range(i + 1, n):
if texto[i] == texto[j]:
dp[i][j] = dp[i + 1][j - 1] + 2
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
return dp[0][n - 1]
print(palindromo_mas_largo("abacdba"))
5
El detalle crucial de este patrón es el orden de cálculo. Como dp[i][j] depende de dp[i + 1][...], la fila i necesita que la fila i + 1 ya esté calculada. Por eso el bucle exterior recorre i de mayor a menor. Si lo recorrieras en orden normal, leerías celdas todavía vacías y el resultado sería incorrecto sin ningún mensaje de error. Una alternativa equivalente es iterar por longitud de intervalo, de los más cortos a los más largos.
Visualmente, la tabla se rellena por diagonales: primero la diagonal principal, con los intervalos de un solo carácter, y después diagonales cada vez más alejadas, hasta llegar a la esquina superior derecha, que representa la cadena completa. Este mismo esquema resuelve problemas como multiplicar matrices en el orden más barato o el juego de tomar monedas de los extremos de una fila.
Patrón 5: transición no constante
Hasta ahora, cada estado dependía de un número fijo de estados anteriores. En este patrón, un estado puede depender de todos los anteriores, y la transición recorre un rango variable.
El ejemplo canónico es la subsecuencia creciente más larga: dada una lista de números, buscamos la longitud de la subsecuencia estrictamente creciente más larga.
Definimos dp[i] como la longitud de la subsecuencia creciente más larga que termina exactamente en la posición i. Para calcularla, revisamos todas las posiciones anteriores j cuyo valor sea menor y extendemos la mejor de ellas.
def creciente_mas_larga(valores: list[int]) -> int:
if not valores:
return 0
dp = [1] * len(valores)
for i in range(len(valores)):
for j in range(i):
if valores[j] < valores[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
print(creciente_mas_larga([3, 10, 2, 1, 20, 4, 6, 7]))
4
Fíjate en un detalle sutil de la definición: la respuesta no está en la última celda, sino en el máximo de todas, porque la mejor subsecuencia puede terminar en cualquier posición. En el ejemplo es 1, 4, 6, 7 o 2, 4, 6, 7.
Esta solución tiene complejidad cuadrática. Existe una versión más rápida, de orden n log n, que mantiene una lista donde la posición k guarda el menor valor final posible de una subsecuencia creciente de longitud k + 1, y usa búsqueda binaria para actualizarla:
from bisect import bisect_left
def creciente_mas_larga_rapida(valores: list[int]) -> int:
finales: list[int] = []
for valor in valores:
posicion = bisect_left(finales, valor)
if posicion == len(finales):
finales.append(valor)
else:
finales[posicion] = valor
return len(finales)
Para listas pequeñas la diferencia es irrelevante, pero con cien mil elementos la versión cuadrática hace del orden de cinco mil millones de comparaciones, mientras que la versión con búsqueda binaria apenas supera el millón y medio.
Patrón 6: problemas tipo mochila
El último patrón agrupa los problemas en los que debes elegir elementos para alcanzar una suma o llenar una capacidad. El estado suele ser dp[s], que representa algo sobre la suma o capacidad s.
El primer ejemplo es la partición en dos subconjuntos de igual suma. Tienes una lista de pesos y quieres saber si puedes repartirlos en dos grupos que pesen exactamente lo mismo. Si la suma total es impar, es imposible. Si es par, el problema se reduce a otro más simple: ¿existe un subconjunto que sume exactamente la mitad?
def se_puede_repartir(pesos: list[int]) -> bool:
total = sum(pesos)
if total % 2:
return False
objetivo = total // 2
alcanzable = [False] * (objetivo + 1)
alcanzable[0] = True
for peso in pesos:
for suma in range(objetivo, peso - 1, -1):
alcanzable[suma] = alcanzable[suma] or alcanzable[suma - peso]
return alcanzable[objetivo]
print(se_puede_repartir([3, 1, 5, 9, 12]))
print(se_puede_repartir([2, 4, 5]))
True
False
Aquí está el detalle más importante del problema de la mochila en su versión clásica: el bucle interior recorre las sumas de mayor a menor. Cada peso solo se puede usar una vez, y al ir hacia abajo garantizamos que alcanzable[suma - peso] todavía refleja el estado anterior a considerar ese peso. Si recorrieras las sumas de menor a mayor, un mismo peso podría usarse varias veces dentro de la misma iteración.
Precisamente ese comportamiento es el que se busca en la variante ilimitada, como el problema del cambio de monedas: con un sistema de monedas dado y un número ilimitado de cada una, ¿cuál es el mínimo de monedas para formar una cantidad?
def minimo_monedas(denominaciones: list[int], monto: int) -> int:
INFINITO = float("inf")
dp = [0] + [INFINITO] * monto
for cantidad in range(1, monto + 1):
for moneda in denominaciones:
if moneda <= cantidad and dp[cantidad - moneda] + 1 < dp[cantidad]:
dp[cantidad] = dp[cantidad - moneda] + 1
return dp[monto] if dp[monto] != INFINITO else -1
print(minimo_monedas([1, 5, 10, 25], 63))
print(minimo_monedas([1, 3, 4], 6))
print(minimo_monedas([4, 7], 5))
6
2
-1
El segundo ejemplo muestra por qué hace falta programación dinámica. Una estrategia voraz que siempre toma la moneda más grande posible daría 4 + 1 + 1, tres monedas, cuando la respuesta óptima es 3 + 3, dos monedas. Con sistemas de monedas como el de muchos países la estrategia voraz funciona, pero no está garantizada en general. El tercer ejemplo devuelve -1 porque con monedas de 4 y 7 no hay forma de formar 5.
Cómo reconocer qué patrón aplicar
Ante un problema nuevo, estas preguntas te ayudarán a identificar el patrón:
- ¿La respuesta para el elemento
idepende de uno o dos elementos anteriores? Transición constante. - ¿Te mueves por una cuadrícula con direcciones restringidas? Cuadrícula.
- ¿Comparas dos cadenas o dos listas? Dos secuencias.
- ¿El problema habla de fragmentos contiguos o de extremos de una secuencia? Intervalos.
- ¿Para cada elemento necesitas revisar todos los anteriores? Transición no constante.
- ¿Eliges elementos para alcanzar una suma, un peso o una capacidad? Mochila.
Otra pista útil son las palabras del enunciado. Expresiones como “número de formas”, “mínimo coste”, “máximo valor”, “¿es posible?” o “la más larga” suelen indicar programación dinámica, sobre todo si una búsqueda exhaustiva tendría complejidad exponencial.
Cuando no reconozcas ningún patrón, vuelve al método básico: escribe primero una función recursiva que resuelva el problema por fuerza bruta, identifica qué parámetros cambian entre llamadas, que serán las dimensiones de tu estado, y añade @cache. En muchos casos eso ya es una solución aceptable.
Errores comunes y cómo evitarlos
Hay errores que se repiten en casi todas las personas que aprenden esta técnica.
Definir el estado de forma ambigua. Si no puedes escribir en una frase qué significa dp[i][j], la transición será incorrecta. Antes de escribir código, anota la definición en un comentario, por ejemplo “longitud de la LCS de a[:i] y b[:j]”.
Olvidar o equivocar los casos base. Muchos errores de uno en uno vienen de aquí. La fila y columna extra para prefijos vacíos, como en LCS, eliminan buena parte de estos problemas.
Calcular en el orden incorrecto. En los problemas de intervalos y en la mochila clásica, el orden de los bucles no es un detalle estético: determina si lees valores ya actualizados o todavía antiguos.
Crear matrices con referencias compartidas. [[0] * n] * m crea m referencias a la misma lista; modificar una fila modifica todas. Usa siempre una comprensión de listas.
Superar el límite de recursión. La memoización con recursión profunda puede provocar un RecursionError en entradas grandes. Puedes aumentar el límite con sys.setrecursionlimit, pero la solución robusta es pasar a tabulación.
Usar @cache con argumentos mutables. El decorador necesita argumentos hashables. Si tu función recibe una lista, convierte la lista en una tupla o, mejor, pasa solo índices y accede a la lista desde fuera de la función.
Confundir el valor óptimo con la solución. Una tabla de programación dinámica normalmente da el valor óptimo, como la longitud o el coste, no la secuencia de decisiones. Para reconstruir la solución, guarda qué opción se tomó en cada celda o recorre la tabla hacia atrás.
Programación dinámica más allá de las entrevistas
Aunque mucha gente la estudia para superar entrevistas técnicas, la programación dinámica está en el corazón de herramientas que usas todos los días.
Las herramientas de diferencias como diff y la comparación de cambios en Git se apoyan en algoritmos de subsecuencia común para mostrar qué líneas cambiaron entre dos versiones de un archivo. Los correctores ortográficos y los buscadores tolerantes a errores usan la distancia de edición para sugerir la palabra que probablemente querías escribir. La bioinformática alinea secuencias de ADN y proteínas con variantes de esos mismos algoritmos.
En el procesamiento del lenguaje y el reconocimiento de voz, el algoritmo de Viterbi, que encuentra la secuencia de estados más probable en un modelo oculto de Márkov, es programación dinámica. Los sistemas de navegación calculan rutas óptimas con algoritmos emparentados, y los optimizadores de consultas de muchas bases de datos usan programación dinámica para decidir en qué orden unir las tablas de una consulta.
Entender los patrones de esta guía te permite no solo resolver ejercicios, sino reconocer estas estructuras cuando aparecen en problemas reales de tu trabajo.
Cómo practicar de forma eficaz
La programación dinámica se aprende resolviendo problemas, pero no de cualquier manera. Estas recomendaciones aceleran mucho el progreso.
Agrupa los ejercicios por patrón. Resolver cinco problemas del mismo patrón seguidos consolida la estructura mucho mejor que saltar entre temas al azar.
Dibuja la tabla a mano antes de programar. Rellenar en papel las primeras filas con un ejemplo pequeño revela la transición y los casos base, y te permite comprobar después que tu código produce los mismos valores.
Imprime la tabla mientras depuras. Una función auxiliar que muestre la matriz con formato te ahorrará horas:
def mostrar_tabla(dp: list[list[int]]) -> None:
for fila in dp:
print(" ".join(f"{valor:3}" for valor in fila))
Escribe primero la versión memoizada y después la tabulada. La primera valida la idea; la segunda te obliga a entender el orden de dependencias.
Analiza siempre la complejidad. Multiplica el número de estados por el trabajo de cada transición. LCS tiene m · n estados con trabajo constante, así que es O(m · n); la versión básica de la subsecuencia creciente tiene n estados con trabajo lineal, así que es O(n²). Este cálculo te dirá si la solución es viable para el tamaño de entrada del problema.
Conclusiones
La programación dinámica deja de ser intimidante cuando la entiendes como una forma sistemática de reutilizar resultados, guiada por cuatro pasos: definir el estado, encontrar la transición, fijar los casos base y decidir el orden de cálculo. Los problemas cambian de enunciado, pero los patrones se repiten.
En esta guía has recorrido seis de ellos con soluciones en Python: la transición constante con la escalera y las propinas, las cuadrículas con el conteo de caminos, las dos secuencias con la subsecuencia común y la distancia de edición, los intervalos con el palíndromo más largo, la transición no constante con la subsecuencia creciente y los problemas tipo mochila con la partición y el cambio de monedas. También has visto cuándo elegir memoización o tabulación, cómo reducir el espacio y qué errores evitar.
Dominar la programación dinámica en Python es una inversión que rinde tanto en entrevistas como en el trabajo diario, porque te enseña a descomponer problemas complejos en piezas que se resuelven una sola vez. Elige un patrón, resuelve varios problemas seguidos dibujando sus tablas y verás cómo la técnica pasa de ser un misterio a convertirse en una herramienta más de tu repertorio.