Programación Dinámica: Optimización de Problemas Algorítmicos Complejos

La programación dinámica transforma problemas exponenciales en soluciones polinomiales mediante el almacenamiento inteligente de resultados intermedios. Es una de las técnicas más poderosas en algoritmia.

1. Definición: ¿Qué es la Programación Dinámica?

Programación Dinámica (DP)

Método para implementar eficientemente un procedimiento recursivo mediante el almacenamiento de resultados parciales.

Principio fundamental: Sustituir tiempo de cómputo por espacio de almacenamiento.

Idea clave: Si un algoritmo recursivo calcula los mismos subproblemas repetidamente, almacenar sus resultados elimina redundancia.

Principio: Trade-off Tiempo vs Espacio

Trade-off Fundamental

Programación Dinámica = Tiempo de cálculo ↔ Espacio de memoria

Guardar resultados intermedios → Evitar recálculos
Costo: Memoria adicional $O(n)$ o $O(n^2)$
Beneficio: Reducción de tiempo exponencial → polinomial

Ejemplo típico:

Sin DP: $O(2^n)$ tiempo, $O(n)$ espacio (recursión)
Con DP: $O(n)$ tiempo, $O(n)$ espacio (tabulación)

Dos Enfoques de Programación Dinámica

Enfoque	Descripción	Implementación	Cuándo usar
Memoización (Top-down)	Recursión + caché de resultados	Recursivo con diccionario	Natural, fácil de implementar
Tabulación (Bottom-up)	Llenar tabla iterativamente	Iterativo con array	Más eficiente, mejor espacio

2. Propósito: Garantizar Optimalidad y Eficiencia

Objetivo de la Programación Dinámica

Resolver problemas de optimización (maximizar/minimizar) garantizando:

✅ Optimalidad global (mejor solución posible)
✅ Eficiencia polinomial (no exponencial)
✅ Corrección demostrable (matemáticamente rigurosa)

Comparación con Otros Métodos

DP vs Otros Métodos de Optimización

Algoritmos Greedy (Voraces):

✅ Muy eficientes: $O(n)$ o $O(n \log n)$
❌ No garantizan optimalidad global
❌ Solo decisiones locales óptimas
Ejemplo: Cambio de monedas puede fallar

Búsqueda Exhaustiva (Backtracking):

✅ Garantiza optimalidad (prueba todo)
❌ Tiempo exponencial $O(2^n)$ o $O(n!)$
❌ Impracticable para $n$ grandes
Ejemplo: TSP, N-Reinas

Programación Dinámica:

✅ Garantiza optimalidad
✅ Eficiencia polinomial $O(n)$ , $O(n^2)$ , $O(n^3)$
✅ Combina lo mejor de ambos mundos
✓ Requiere subestructura óptima y subproblemas solapados

3. Requisitos: ¿Cuándo Aplicar Programación Dinámica?

Condiciones Necesarias para DP

Para que la programación dinámica sea efectiva, el problema debe tener:

1. Subproblemas Solapados (Overlapping Subproblems)

El mismo subproblema se calcula múltiples veces
Sin solapamiento → DP no ayuda (ej: MergeSort)

2. Subestructura Óptima (Optimal Substructure)

La solución óptima contiene soluciones óptimas de subproblemas
Ejemplo: Camino más corto se compone de caminos más cortos

3. Espacio de Parámetros Acotado

Número de subproblemas distintos es polinomial
Si es exponencial → DP no mejora significativamente

Objetos Ideales para DP

Estructuras con orden natural para DP

OBJETOS IDEALES PARA PROGRAMACIÓN DINÁMICA:

1. Cadenas de caracteres:
   - Orden: izquierda → derecha
   - Ejemplo: Subsecuencia común más larga (LCS)
   - DP[i][j] = considerando primeros i,j caracteres

2. Secuencias de números:
   - Orden: índice natural
   - Ejemplo: Subsecuencia creciente más larga (LIS)
   - DP[i] = mejor solución terminando en posición i

3. Árboles con raíz:
   - Orden: estructura jerárquica padre-hijo
   - Ejemplo: Diámetro de árbol
   - DP[nodo] = mejor solución en subárbol

4. Grafos con DAG:
   - Orden: topológico
   - Ejemplo: Caminos más largos en DAG
   - DP[v] = procesar en orden topológico

OBJETOS PROBLEMÁTICOS:
  ✗ Grafos generales (sin orden natural)
  ✗ Conjuntos sin estructura (permutaciones arbitrarias)
  ✗ Problemas donde el "estado" es complejo y grande

4. Metodología: Pasos para Diseñar Algoritmos DP

Metodología de 5 Pasos

1. Definir el Estado

¿Qué información necesito almacenar?
DP[i], DP[i][j], DP[estado…]?

2. Formular la Recurrencia

Expresar DP[…] en términos de subproblemas más pequeños
Identificar casos base

3. Verificar Condiciones

¿Hay subproblemas solapados?
¿Hay subestructura óptima?
¿Número de estados es polinomial?

4. Definir Orden de Evaluación

Top-down (memoización): recursión con caché
Bottom-up (tabulación): orden que garantice dependencias

5. Implementar y Optimizar

Escribir código
Optimizar espacio si es posible
Reconstruir solución si es necesario

5. Ejemplo Fundamental: Fibonacci

Secuencia de Fibonacci

Definición recursiva: $F_n = F_{n-1} + F_{n-2}$

Casos base: $F_0 = 0$ , $F_1 = 1$

Secuencia: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

Implementación 1: Recursión Ingenua

Fibonacci recursivo (INEFICIENTE)

def fibonacci_recursivo(n):
    """
    Implementación recursiva directa
    ADVERTENCIA: Extremadamente ineficiente para n > 35
    """
    if n <= 1:
        return n

    return fibonacci_recursivo(n - 1) + fibonacci_recursivo(n - 2)

# Demostración con trazado
def fibonacci_trace(n, depth=0):
    """Versión con trazado para visualizar redundancia"""
    indent = "  " * depth
    print(f"{indent}fib({n})")

    if n <= 1:
        return n

    left = fibonacci_trace(n - 1, depth + 1)
    right = fibonacci_trace(n - 2, depth + 1)

    return left + right

print("="*60)
print("FIBONACCI RECURSIVO: Visualización de Redundancia")
print("="*60 + "\n")

print("Árbol de llamadas para fib(5):\n")
result = fibonacci_trace(5)
print(f"\nResultado: {result}")

print("\n" + "="*60)
print("ANÁLISIS DE COMPLEJIDAD:")
print("="*60)
print("""
Tiempo: O(φ^n) donde φ ≈ 1.618 (proporción áurea)
        Aproximadamente O(1.6^n) - EXPONENCIAL

Espacio: O(n) - profundidad de recursión

Problema: Recalcula subproblemas múltiples veces
  - fib(3) se calcula 2 veces en fib(5)
  - fib(2) se calcula 3 veces en fib(5)
  - fib(1) se calcula 5 veces en fib(5)

Para fib(40):
  - Más de 1 BILLÓN de llamadas
  - Tiempo: varios segundos
""")

# Contar llamadas
call_count = 0

def fibonacci_count(n):
    global call_count
    call_count += 1

    if n <= 1:
        return n

    return fibonacci_count(n - 1) + fibonacci_count(n - 2)

print("\n" + "="*60)
print("NÚMERO DE LLAMADAS:")
print("="*60 + "\n")

for n in [5, 10, 15, 20, 25, 30]:
    call_count = 0
    result = fibonacci_count(n)
    print(f"fib({n:2d}) = {result:8d} | Llamadas: {call_count:12,d}")

Árbol de llamadas para fib(5):

                    fib(5)
                    /    \
                   /      \
              fib(4)      fib(3)  ← REPETIDO
              /    \      /    \
             /      \    /      \
        fib(3)   fib(2) fib(2) fib(1)
        /   \    /   \
       /     \  /     \
   fib(2) fib(1) fib(1) fib(0)
   /   \
  /     \
fib(1) fib(0)

Llamadas totales: 15
Únicos: fib(0), fib(1), fib(2), fib(3), fib(4), fib(5) = 6

Redundancia: 15 llamadas para 6 valores únicos
Factor: 2.5x de trabajo redundante

Para fib(10):

Llamadas: 177
Únicos: 11
Redundancia: 16x

Para fib(40):

Llamadas: 331,160,281 (más de 300 millones)
Únicos: 41
Redundancia: 8 millones de veces

Implementación 2: Memoización (Top-Down DP)

Fibonacci con memoización

def fibonacci_memoization(n, memo=None):
    """
    Fibonacci con memoización (top-down DP)
    Guardar resultados en diccionario
    """
    if memo is None:
        memo = {}
    
    # Ya calculado
    if n in memo:
        return memo[n]
    
    # Casos base
    if n <= 1:
        return n
    
    # Calcular y guardar
    memo[n] = fibonacci_memoization(n - 1, memo) + fibonacci_memoization(n - 2, memo)
    
    return memo[n]

# Versión con decorador (Python idiomático)

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_lru(n):
"""Fibonacci con decorador @lru_cache"""
if n <= 1:
return n

    return fibonacci_lru(n - 1) + fibonacci_lru(n - 2)

print("="*60)
print("FIBONACCI CON MEMOIZACIÓN (Top-Down DP)")
print("="*60 + "\n")

import time

# Comparar tiempos

valores = [10, 20, 30, 35]

print(f"{'n':<5} {'Recursivo':<15} {'Memoización':<15} {'Mejora':<10}")
print("-" \* 50)

for n in valores: # Memoización (siempre rápida)
start = time.time()
result_memo = fibonacci_memoization(n)
time_memo = time.time() - start

    # Recursivo (solo para n pequeño)
    if n <= 35:
        start = time.time()
        result_rec = fibonacci_recursivo(n)
        time_rec = time.time() - start

        mejora = time_rec / time_memo if time_memo > 0 else float('inf')
        print(f"{n:<5} {time_rec:<15.6f} {time_memo:<15.8f} {mejora:>8.0f}x")
    else:
        print(f"{n:<5} {'TOO SLOW':<15} {time_memo:<15.8f} {'∞':<10}")

print("\n" + "="*60)
print("COMPLEJIDAD CON MEMOIZACIÓN:")
print("="*60)
print("""
Tiempo: O(n) - cada valor se calcula UNA sola vez
Espacio: O(n) - almacenar n valores + recursión

Mejora: De O(1.6^n) a O(n) - ENORME diferencia

Ejemplo fib(40):

- Sin memo: ~1.5 segundos
- Con memo: ~0.00001 segundos
- Mejora: 150,000x más rápido
  """)

Implementación 3: Tabulación (Bottom-Up DP)

Fibonacci con tabulación

def fibonacci_tabulation(n):
    """
    Fibonacci con tabulación (bottom-up DP)
    Llenar tabla iterativamente
    """
    if n <= 1:
        return n

    # Crear tabla
    dp = [0] * (n + 1)

    # Casos base
    dp[0] = 0
    dp[1] = 1

    # Llenar tabla de abajo hacia arriba
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

def fibonacci_optimized(n):
    """
    Fibonacci optimizado en espacio
    Solo necesitamos los últimos 2 valores
    """
    if n <= 1:
        return n

    # Solo guardar 2 valores anteriores
    prev2 = 0  # fib(0)
    prev1 = 1  # fib(1)

    for i in range(2, n + 1):
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current

    return prev1

print("="*60)
print("FIBONACCI CON TABULACIÓN (Bottom-Up DP)")
print("="*60 + "\n")

# Demostrar construcción de tabla
n = 10
print(f"Construyendo tabla para fib({n}):\n")

dp = [0] * (n + 1)
dp[0] = 0
dp[1] = 1

print(f"Inicialización:")
print(f"  dp[0] = {dp[0]}")
print(f"  dp[1] = {dp[1]}")
print()

for i in range(2, n + 1):
    dp[i] = dp[i - 1] + dp[i - 2]
    print(f"  dp[{i}] = dp[{i-1}] + dp[{i-2}] = {dp[i-1]} + {dp[i-2]} = {dp[i]}")

print(f"\nTabla completa: {dp}")
print(f"Resultado: fib({n}) = {dp[n]}")

print("\n" + "="*60)
print("COMPARACIÓN DE ENFOQUES:")
print("="*60 + "\n")

print(f"{'n':<6} {'Tabulación':<15} {'Optimizado':<15} {'Resultado':<12}")
print("-" * 50)

for n in [10, 50, 100, 500, 1000]:
    start = time.time()
    result_tab = fibonacci_tabulation(n)
    time_tab = time.time() - start

    start = time.time()
    result_opt = fibonacci_optimized(n)
    time_opt = time.time() - start

    print(f"{n:<6} {time_tab:<15.8f} {time_opt:<15.8f} {result_tab}")

print("\n" + "="*60)
print("OPTIMIZACIÓN DE ESPACIO:")
print("="*60)
print("""
Tabulación completa:
  - Tiempo: O(n)
  - Espacio: O(n) - array completo
  - Ventaja: Puede reconstruir solución

Tabulación optimizada:
  - Tiempo: O(n)
  - Espacio: O(1) - solo 2 variables
  - Ventaja: Mínima memoria
  - Desventaja: No puede reconstruir pasos intermedios
""")

Quiz

¿Cuál es la mejora de complejidad temporal al usar programación dinámica en Fibonacci?

6. Comparación Visual: Recursión vs DP

Comparación lado a lado

═══════════════════════════════════════════════════════════════
RECURSIÓN INGENUA vs PROGRAMACIÓN DINÁMICA
═══════════════════════════════════════════════════════════════

┌─────────────────────────────────┬────────────────────────────────┐
│   RECURSIÓN INGENUA          │   PROGRAMACIÓN DINÁMICA     │
├─────────────────────────────────┼────────────────────────────────┤
│ Árbol de recursión:           │ Evaluación lineal:           │
│                                 │                                │
│       fib(5)                    │ i=0: dp[0] = 0                 │
│       /    \                    │ i=1: dp[1] = 1                 │
│  fib(4)  fib(3) ← REPETIDO    │ i=2: dp[2] = 0+1 = 1           │
│   /  \    /  \                 │ i=3: dp[3] = 1+1 = 2           │
│ fib(3) fib(2) ...              │ i=4: dp[4] = 1+2 = 3           │
│ (múltiples copias)             │ i=5: dp[5] = 2+3 = 5           │
│                                 │                                │
│ Llamadas: 15                    │ Operaciones: 5                 │
│ Redundancia: 2.5x               │ Redundancia: 0                 │
├─────────────────────────────────┼────────────────────────────────┤
│ Complejidad Temporal:           │ Complejidad Temporal:          │
│ O(1.6^n) - EXPONENCIAL          │ O(n) - LINEAL                  │
│                                 │                                │
│ Complejidad Espacial:           │ Complejidad Espacial:          │
│ O(n) - pila recursión           │ O(n) - tabla o O(1) optim      │
├─────────────────────────────────┼────────────────────────────────┤
│ fib(10): 177 llamadas           │ fib(10): 10 operaciones        │
│ fib(20): 21,891 llamadas        │ fib(20): 20 operaciones        │
│ fib(30): 2,692,537 llamadas     │ fib(30): 30 operaciones        │
│ fib(40): 331,160,281 llam.      │ fib(40): 40 operaciones        │
│                                 │                                │
│ Tiempo fib(40): ~1.5 segundos   │ Tiempo fib(40): ~0.00001 seg   │
└─────────────────────────────────┴────────────────────────────────┘

LECCIÓN: La diferencia no es marginal, es EXPONENCIAL vs LINEAL
Para n=40: mejora de 150,000x en velocidad

7. Tabla Resumen: Enfoques de DP

Aspecto	Recursión Ingenua	Memoización	Tabulación	Tabulación Optimizada
Enfoque	Directo	Top-down + caché	Bottom-up	Bottom-up + reducción
Implementación	Recursiva	Recursiva + dict	Iterativa	Iterativa mínima
Tiempo	$O(1.6^n)$	$O(n)$	$O(n)$	$O(n)$
Espacio	$O(n)$ pila	$O(n)$ memo	$O(n)$ tabla	$O(1)$
Facilidad	Trivial	Fácil	Media	Requiere análisis
Mejor para	❌ Nunca usar	Prototipos rápidos	Producción	Memoria limitada

8. Advertencias y Limitaciones

Cuándo DP NO es la Solución

Programación Dinámica NO funciona bien cuando:

1. Sin Subproblemas Solapados

Ejemplo: MergeSort, QuickSort
Cada subproblema es único
No hay redundancia que eliminar

2. Espacio de Estados Exponencial

Ejemplo: TSP completo (necesita rastrear subconjuntos)
Estado: DP[visitados][último] donde visitados es subconjunto
Número de estados: $2^n \times n$ = exponencial
DP[1024][10] para n=10 ciudades

3. Sin Orden Natural

Grafos generales sin estructura
Permutaciones sin restricciones
El “estado” es complejo y grande

4. Estado Requiere Información Compleja

Necesitas rastrear toda la solución parcial
No se puede resumir en pocos parámetros
Ejemplo: Sudoku (necesitas el tablero completo)

Advertencia: Complejidad Oculta

Cuidado con el espacio de estados:

Fibonacci simple:

Estados: $n$ (solo un parámetro)
Espacio: $O(n)$ ✓ Manejable

Problema de mochila:

Estados: $n \times W$ (items × capacidad)
Espacio: $O(nW)$ ✓ Pseudo-polinomial

TSP con DP:

Estados: $2^n \times n$ (subconjuntos × último nodo)
Espacio: $O(2^n \cdot n)$ ✗ Exponencial
Para n=20: ~20 millones de estados
Para n=30: ~32 mil millones de estados

Regla práctica: Si el número de estados distintos es exponencial, DP no ayuda significativamente.

9. Metodología Aplicada: Checklist

Checklist para diseñar algoritmos DP

"""
CHECKLIST PARA PROGRAMACIÓN DINÁMICA

□ PASO 1: IDENTIFICAR SUBPROBLEMAS SOLAPADOS
  ¿El algoritmo recursivo calcula lo mismo múltiples veces?
  Ejemplo: fib(5) llama a fib(3) dos veces

  SI NO hay solapamiento → DP no ayuda

□ PASO 2: VERIFICAR SUBESTRUCTURA ÓPTIMA
  ¿La solución óptima contiene soluciones óptimas de subproblemas?
  Ejemplo: Camino más corto A→C = A→B + B→C (óptimos)

  SI NO hay subestructura óptima → DP no garantiza óptimo

□ PASO 3: DEFINIR EL ESTADO
  ¿Qué información necesito almacenar?
  - Un parámetro: dp[i]
  - Dos parámetros: dp[i][j]
  - Múltiples: dp[i][j][k]...

  Ejemplo Fibonacci: dp[n] = n-ésimo número

□ PASO 4: FORMULAR LA RECURRENCIA
  Expresar dp[...] en términos de subproblemas

  Ejemplo Fibonacci: dp[n] = dp[n-1] + dp[n-2]

  Casos base: dp[0] = 0, dp[1] = 1

□ PASO 5: CONTAR ESTADOS
  ¿Cuántos estados distintos hay?
  - Polinomial (n, n², n³) → DP funciona ✓
  - Exponencial (2^n, n!) → DP problemático ✗

  Ejemplo Fibonacci: n estados → O(n) ✓

□ PASO 6: DETERMINAR ORDEN DE EVALUACIÓN
  Top-down (memoización):
    - Recursión natural
    - Agregar caché (dict o @lru_cache)

  Bottom-up (tabulación):
    - Identificar dependencias
    - Evaluar en orden que garantice datos disponibles

  Ejemplo Fibonacci: i = 0, 1, 2, ..., n

□ PASO 7: IMPLEMENTAR
  Código limpio con:
  - Casos base claros
  - Índices correctos
  - Límites verificados

□ PASO 8: OPTIMIZAR ESPACIO (opcional)
  ¿Se puede reducir espacio?
  - Solo necesitas fila anterior? → Reducir O(n²) a O(n)
  - Solo necesitas k valores? → Reducir O(n) a O(k)

  Ejemplo Fibonacci: O(n) → O(1) con 2 variables

□ PASO 9: RECONSTRUIR SOLUCIÓN (si necesario)
  ¿Solo el valor óptimo o también la solución?
  - Valor: basta con dp[n]
  - Solución: guardar decisiones o reconstruir con backtracking
"""

Quiz

¿Cuáles son las DOS condiciones necesarias para que la programación dinámica sea efectiva?

10. Ejemplo Adicional: Subsecuencia Común Más Larga (LCS)

LCS: Problema clásico de DP en dos dimensiones

def lcs_recursivo(X, Y, m, n):
    """
    LCS recursivo ingenuo (INEFICIENTE)
    X, Y: cadenas
    m, n: longitudes a considerar
    """
    if m == 0 or n == 0:
        return 0
    
    if X[m - 1] == Y[n - 1]:
        return 1 + lcs_recursivo(X, Y, m - 1, n - 1)
    else:
        return max(lcs_recursivo(X, Y, m - 1, n),
                   lcs_recursivo(X, Y, m, n - 1))

def lcs_dp(X, Y):
"""
LCS con programación dinámica (EFICIENTE)
Retorna longitud y la subsecuencia
"""
m, n = len(X), len(Y)

    # Crear tabla DP
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Llenar tabla
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    # Reconstruir subsecuencia
    lcs = []
    i, j = m, n

    while i > 0 and j > 0:
        if X[i - 1] == Y[j - 1]:
            lcs.append(X[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1

    lcs.reverse()

    return dp[m][n], ''.join(lcs), dp

print("="*60)
print("LONGEST COMMON SUBSEQUENCE (LCS)")
print("="*60 + "\n")

X = "AGGTAB"
Y = "GXTXAYB"

print(f"Cadena X: {X}")
print(f"Cadena Y: {Y}")
print()

# Calcular LCS

length, subsequence, dp_table = lcs_dp(X, Y)

print(f"Longitud de LCS: {length}")
print(f"Subsecuencia: {subsequence}")
print()

# Mostrar tabla DP

print("Tabla DP:")
print(f"{'':>4}", end="")
for char in Y:
print(f"{char:>3}", end="")
print()

for i in range(len(X) + 1):
if i > 0:
print(f"{X[i-1]:>3}", end=" ")
else:
print(f"{'':>3}", end=" ")

    for j in range(len(Y) + 1):
        print(f"{dp_table[i][j]:>3}", end="")
    print()

print("\n" + "="*60)
print("ANÁLISIS:")
print("="*60)
print(f"""
Recursivo ingenuo:

- Tiempo: O(2^(m+n)) - exponencial
- Recalcula subproblemas masivamente

Programación Dinámica:

- Tiempo: O(m×n) - cuadrático
- Espacio: O(m×n) - tabla 2D
- Cada celda se calcula UNA vez

Para X={len(X)}, Y={len(Y)}:

- Estados: {(len(X)+1) \* (len(Y)+1)} (tabla completa)
- Operaciones: {len(X) \* len(Y)}
- Reconstrucción: O(m+n)
  """)

Problemas Clásicos de Programación Dinámica:

1. Problema de la Mochila (0/1 Knapsack)

Estado: dp[i][w] = máximo valor con primeros i items y capacidad w
Recurrencia: dp[i][w] = max(dp[i-1][w], dp[i-1][w-peso[i]] + valor[i])
Complejidad: $O(nW)$ pseudo-polinomial

2. Subsecuencia Creciente Más Larga (LIS)

Estado: dp[i] = longitud de LIS terminando en i
Recurrencia: dp[i] = max(dp[j] + 1) para j < i y arr[j] < arr[i]
Complejidad: $O(n^2)$ básico, $O(n \log n)$ optimizado

3. Partición de Subconjuntos

¿Se puede particionar array en dos subconjuntos con suma igual?
Estado: dp[i][sum] = ¿es posible suma con primeros i elementos?
Complejidad: $O(n \times \text{suma})$

4. Editar Distancia (Edit Distance)

Mínimo de inserciones/borrados/sustituciones
Estado: dp[i][j] = distancia entre X[1..i] y Y[1..j]
Complejidad: $O(mn)$

5. Corte de Varilla (Rod Cutting)

Maximizar precio cortando varilla
Estado: dp[n] = máximo precio para longitud n
Complejidad: $O(n^2)$

6. Multiplicación de Matrices en Cadena

Minimizar operaciones escalares
Estado: dp[i][j] = mínimo costo para matrices i a j
Complejidad: $O(n^3)$

7. Cambio de Monedas (Coin Change)

Mínimo número de monedas para dar cambio
Estado: dp[amount] = mínimo de monedas para amount
Complejidad: $O(n \times \text{amount})$

8. Camino Máximo en Triángulo

Suma máxima desde arriba hasta abajo
Estado: dp[i][j] = suma máxima hasta (i,j)
Complejidad: $O(n^2)$

11. Cierre: Lecciones Fundamentales

Conclusiones Clave

1. DP = Recursión + Memoria

Programación Dinámica no es magia, es eliminar redundancia mediante almacenamiento inteligente.

2. Transformación Exponencial → Polinomial

La mejora típica: $O(2^n)$ → $O(n)$ , $O(n \times 2^n)$ → $O(n^2)$

3. Verificar Condiciones

✓ Subproblemas solapados
✓ Subestructura óptima
✓ Espacio de estados polinomial

4. Dos Enfoques Válidos

Memoización: Más natural, fácil de implementar
Tabulación: Más eficiente, mejor control de espacio

5. Optimización de Espacio

A menudo se puede reducir: $O(n^2)$ → $O(n)$ , $O(n)$ → $O(1)$

6. Conocer Limitaciones

DP no es universal. Si el espacio de estados es exponencial o no hay estructura, considerar otras técnicas.

Advertencia Final

La implementación correcta requiere:

✓ Formulación precisa de la recurrencia
✓ Casos base correctos
✓ Índices manejados cuidadosamente
✓ Orden de evaluación válido

Error común: Confundir índices (0-indexed vs 1-indexed) o límites puede llevar a bugs sutiles. Probar exhaustivamente con casos pequeños conocidos.

Resumen Final

Conceptos Dominados

✓ Definición de DP:

Recursión + almacenamiento de resultados
Trade-off: tiempo ↔ espacio
Elimina redundancia computacional

✓ Condiciones Necesarias:

Subproblemas solapados
Subestructura óptima
Espacio de estados polinomial

✓ Dos Enfoques:

Memoización (top-down): recursión + caché
Tabulación (bottom-up): iterativo

✓ Fibonacci como Ejemplo:

Recursivo: $O(1.6^n)$ exponencial
DP: $O(n)$ lineal
Mejora: 150,000x para n=40

✓ Metodología:

Definir estado
Formular recurrencia
Verificar condiciones
Implementar con orden correcto
Optimizar espacio si posible

✓ Limitaciones:

No funciona sin solapamiento
No funciona con estado exponencial
Requiere orden natural en el problema

Quiz

¿Cuál es la diferencia principal entre memoización y tabulación?

¡Felicitaciones!

Has completado programación dinámica. Ahora dominas:

El concepto fundamental de DP: eliminar redundancia
Las dos condiciones necesarias para aplicar DP
Diferencia entre memoización y tabulación
Análisis de complejidad: identificar mejora exponencial→polinomial
Metodología para diseñar algoritmos DP
Optimización de espacio en DP
Cuándo DP es apropiado y cuándo no
Fibonacci, LCS y otros problemas clásicos

Próximo paso: Aplicar DP a problemas más complejos como Knapsack, Edit Distance, Matrix Chain Multiplication, y explorar técnicas avanzadas como DP con bitmasks y DP sobre árboles.

Explorar

Blog

Roadmaps

Programación Dinámica: Optimización con Memoización

Programación Dinámica: Optimización de Problemas Algorítmicos Complejos

1. Definición: ¿Qué es la Programación Dinámica?

Programación Dinámica (DP)

Principio: Trade-off Tiempo vs Espacio

Trade-off Fundamental

Dos Enfoques de Programación Dinámica

2. Propósito: Garantizar Optimalidad y Eficiencia

Objetivo de la Programación Dinámica

Comparación con Otros Métodos

DP vs Otros Métodos de Optimización

3. Requisitos: ¿Cuándo Aplicar Programación Dinámica?

Condiciones Necesarias para DP

Objetos Ideales para DP

4. Metodología: Pasos para Diseñar Algoritmos DP

Metodología de 5 Pasos

5. Ejemplo Fundamental: Fibonacci

Secuencia de Fibonacci

Implementación 1: Recursión Ingenua

Implementación 2: Memoización (Top-Down DP)

Implementación 3: Tabulación (Bottom-Up DP)

¿Cuál es la mejora de complejidad temporal al usar programación dinámica en Fibonacci?

6. Comparación Visual: Recursión vs DP

7. Tabla Resumen: Enfoques de DP

8. Advertencias y Limitaciones

Cuándo DP NO es la Solución

Advertencia: Complejidad Oculta

9. Metodología Aplicada: Checklist

¿Cuáles son las DOS condiciones necesarias para que la programación dinámica sea efectiva?

10. Ejemplo Adicional: Subsecuencia Común Más Larga (LCS)

11. Cierre: Lecciones Fundamentales

Conclusiones Clave

Advertencia Final

Resumen Final

Conceptos Dominados

¿Cuál es la diferencia principal entre memoización y tabulación?

¡Felicitaciones!