¿Qué es la programación dinámica en palabras sencillas?
Imagina que estás calculando el factorial del número 5.
Para ello, se necesita: 5 × 4 × 3 × 2 × 1. Y ahora se le pide que calcule el factorial de 6. Sería una tontería volver a contar todo de nuevo, ¿verdad? Ya sabes que 5! = 120, solo tienes que multiplicar por 6.
Programación dinámica (PD) — es exactamente el mismo enfoque: resolvemos un problema complejo, dividiéndolo en subtareas, y memorizamos los resultadospara no contar lo mismo dos veces.
Los principales signos de las tareas en el PD:
🎯 Subestructura óptima
La solución de un gran problema consiste en soluciones de pequeñas subtareas
🔄 Subtareas superpuestas
Las mismas subtareas se repiten muchas veces
⚡ Necesitamos encontrar el equilibrio
Máximo, mínimo o número de métodos
Dos enfoques para la PD: memorización y tabulación
1. Memorización (de arriba a abajo)
Esto es recursión + almacenamiento en caché de resultados. Comenzamos con una gran tarea y bajamos a los casos básicos.
def fibonacci_memo(n, memo={}):
# Casos básicos
if n <= 1:
return n
# Comprobando caché
if n in memo:
return memo[n]
# Calcular y guardar
memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
return memo[n]
print(fibonacci_memo(50)) # ¡Al instante!Cuándo usar: cuando la lógica de la tarea es intuitiva a través de la recursión.
2. Tabulación (de abajo hacia arriba)
Construimos una tabla de soluciones desde los casos básicos hasta la respuesta final. ¡Sin recurrencia!
def fibonacci_table(n):
if n <= 1:
return n
# Crear una tabla
dp = [0] * (n + 1)
dp[0] = 0
dp[1] = 1
# Rellenar de abajo hacia arriba
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
print(fibonacci_table(50))Cuándo usar: cuando se necesita el máximo rendimiento y control de la memoria.
Problemas clásicos de PD que debe conocer en 2026
Tarea 1: Números de Fibonacci
Dificultad sin DP: ¡O(2ⁿ) es exponencial!
Dificultad con DP: ¡O(n) es lineal!
Ya hemos visto la solución anteriormente. Esta es la tarea ideal para empezar.
Tarea 2: Problema de la mochila (Knapsack Problem)
Eres un ladrón con una mochila de capacidad W. Hay objetos con peso y valor. ¿Cómo tomar el valor máximo?
def knapsack(weights, values, capacity):
n = len(weights)
# dp[i][w] = valor máximo para i artículos y capacidad w
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(1, capacity + 1):
# No tomamos el objeto
dp[i][w] = dp[i-1][w]
# Tomamos el objeto si cabe
if weights[i-1] <= w:
dp[i][w] = max(
dp[i][w],
dp[i-1][w - weights[i-1]] + values[i-1]
)
return dp[n][capacity]
weights = [1, 2, 3, 5]
values = [10, 5, 15, 7]
capacity = 7
print(knapsack(weights, values, capacity)) # 32Aplicación en la realidad: asignación de recursos, planificación presupuestaria, optimización de la carga del servidor.
Tarea 3: Subsecuencia común más larga (LCS)
Encuentra la subsecuencia común más larga de dos cadenas. ¡Base para git diff!
def lcs(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[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(lcs("ABCDGH", "AEDFHR")) # 3 (ADH)Aplicación: sistemas de control de versiones, verificación de plagio, bioinformática (comparación de ADN).
Tarea 4: Coin Change (Cambio de monedas)
Hay monedas de diferentes valores. ¿De cuántas maneras se puede obtener la cantidad?
def coin_change(coins, amount):
# dp[i] = número mínimo de monedas para la cantidad i
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # Para la cantidad 0 se necesitan 0 monedas
for i in range(1, amount + 1):
for coin in coins:
if coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
coins = [1, 2, 5]
amount = 11print(coin_change(coins, amount)) # 3 (5+5+1)Aplicación: aplicaciones fintech, sistemas de caja, optimización de transacciones.
Tarea 5: Edit Distance (Distancia de Levenshtein)
Número mínimo de operaciones para convertir una línea en otra.
def edit_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Inicialización
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
# Rellenar la tabla
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(
dp[i-1][j], # eliminación
dp[i][j-1], # inserción
dp[i-1][j-1] # reemplazo
)
return dp[m][n]
print(edit_distance("kitten", "sitting")) # 3Aplicación: corrección de errores tipográficos, motores de búsqueda, autocompletar.
Método paso a paso para resolver problemas en el PD
Paso 1: Encuentra una solución recursiva
Primero, simplemente resuelve el problema con la recursividad sin pensar en la optimización.
# Versión no optimizada de fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)Paso 2: Añadir memorización
Añada un diccionario para almacenar los resultados.
def fib_memo(n, memo={}):
if n <= 1:
return n
if n not in memo:
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]Paso 3: Convertir en tabulador (opcional)
Traducir a un enfoque iterativo con una matriz.
def fib_table(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]Paso 4: Optimiza la memoria
A menudo se puede usar O(1) de memoria en lugar de O(n).
def fib_optimized(n):
if n <= 1:
return n
prev2, prev1 = 0, 1
for _ in range(2, n + 1):
current = prev1 + prev2
prev2, prev1 = prev1, current
return prev1Patrones clave de DP en 2026
1D DP
Matriz unidimensional
Números de Fibonacci
Climbing Stairs
House Robber
2D DP
Matriz bidimensional
Longest Common Subsequence
Edit Distance
Knapsack Problem
DP en líneas
Trabajo con texto
Palindrome Subsequences
String Matching
Wildcard Matching
DP en árboles
Estructuras arbóreas
Binary Tree Maximum Path Sum
Diameter of Binary Tree
DP en los gráficos
Algoritmos de grafos
Shortest Path (Bellman-Ford)
Traveling Salesman Problem
Errores típicos de los principiantes
Error 1: Olvidar los casos básicos
def fib(n):
return fib(n-1) + fib(n-2)
# ¡Recursión infinita!Correcto
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)Error 2: Tamaño de tabla incorrecto
dp = [0] * n
# Si necesita índices 0..n,
# ¡Se necesita el tamaño n+1!Correcto
dp = [0] * (n + 1)Error 3: No comprobar los límites
if dp[i-1]:
# ¿Qué pasa si i = 0?Correcto
if i > 0 and dp[i-1]:Consejos prácticos para entrevistas.
Dibuja una tabla en papel — la visualización ayuda a encontrar dependencias
Empieza con ejemplos pequeños — fib(0), fib(1), fib(2)...
Busca la fórmula de recurrencia — ¿Cómo depende dp[i] de los valores anteriores?
Expresa la lógica en voz alta — esto muestra el curso de tus pensamientos
No tengas miedo de escribir una solución no óptima al principio — luego se puede mejorar
Versión JavaScript para desarrolladores web.
Muchos principiantes trabajan con JavaScript, así que aquí hay un ejemplo en JS:
// Memorizaciónfunction fibMemo(n, memo = {}) {
if (n <= 1) return n;
if (memo[n]) return memo[n];
memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
return memo[n];
}
// Tabulaciónfunction fibTable(n) {
if (n <= 1) return n;
const dp = new Array(n + 1).fill(0);
dp[1] = 1;
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
// Versión optimizada (memoria O(1))function fibOptimized(n) {
if (n <= 1) return n;
let prev2 = 0, prev1 = 1;
for (let i = 2; i <= n; i++) {
const current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return prev1;
}
console.log(fibOptimized(50)); // 12586269025Conclusión.
La programación dinámica no es magia, sino un enfoque lógico para resolver problemas. Puntos clave:
Divide en subtareas — encuentra el patrón de repetición
Guarda los resultados — no cuentes dos veces
Empieza con la recursividad — luego optimiza
Entrena con regularidad — La DP requiere práctica
Después de dominar la programación dinámica, usted:
✅ Aprobarás la mayoría de las entrevistas técnicas
✅ Podrás optimizar las tareas reales en la producción
✅ Comprenderás cómo funcionan las entrañas de muchas bibliotecas y marcos
✅ Aprende a pensar algorítmicamente
Recuerda: cada algoritmo alguna vez pareció complejo incluso para los mejores desarrolladores. Lo principal es la práctica y la paciencia.
Puedes estudiar programación dinámica y muchos otros temas importantes en Kodik — una plataforma educativa con cursos prácticos para desarrolladores. ¡Creamos contenido que realmente ayuda en las entrevistas y en el trabajo!
📱 Y también tenemos un genial Canal de Telegram con una comunidad amistosa donde:
Analizamos las tareas de las entrevistas
Compartimos artículos útiles
Nos ayudamos mutuamente a crecer
Discutimos las últimas tendencias en el desarrollo
¡Únete a la comunidad de desarrolladores que crecen juntos! 💪