La programación dinámica (en inglés: Dynamic programming, abreviado DP) es un método utilizado en matemáticas, ciencias de la gestión, ciencias de la computación, economía y bioinformática para resolver problemas complejos descomponiendo el problema original en subproblemas relativamente simples.

Imagina que estás subiendo unanescalera de [n] escalones. Cada vez puedes subir1escalones o2escalones.

Entonces, ¿cuántos métodos diferentes hay para llegar a la cima?

Si piensas desde el objetivo del nivel más alto (elnnivel) al empezar a pensar, puede parecer complicado.

Pero si cambiamos de enfoque:Para llegar alnescalón n, solo puedes desde eln-1escalón n-1 subir un escalón, o desde eln-2escalón n-2 subir dos escalones. Por lo tanto, el número de métodos para llegar alnescalón n es igual al número de métodos para llegar aln-1escalón n-1 más el número de métodos para llegar aln-2escalón n-2.

Estaforma de descomponer un gran problema en subproblemas superpuestos y, al guardar las soluciones de los subproblemas, evitar el cálculo repetido, resolviendo así eficientemente el problema originales la programación dinámica (Dynamic Programming, abreviado DP).

Idea central

El núcleo de la programación dinámica esrecordar las soluciones ya calculadas 。

La programación dinámica se utiliza generalmente para resolver problemas con las siguientes propiedades:

  1. Subproblemas superpuestos: durante el proceso de resolución recursiva, el mismo subproblema se calcula múltiples veces.
  2. Subestructura óptima: la solución óptima de un problema contiene la solución óptima de sus subproblemas.

Podemos usar un diagrama de flujo simple para entender el enfoque de resolución de problemas de la programación dinámica:

La figura anterior muestra los pasos típicos para resolver un problema de programación dinámica: comenzar definiendo el problema, encontrar la estructura de los subproblemas mediante el análisis, formalizarla con estados y la ecuación de transición de estados, y finalmente obtener la respuesta mediante condiciones iniciales claras y el orden de cálculo.


De la recursión a la programación dinámica: el problema de subir escaleras

Usemos el clásico"subir escaleras"problema para experimentar el proceso de optimización desde la recursión hasta la programación dinámica.

Descripción del problema

Supón que estás subiendo escaleras. Necesitasnescalones para llegar a la cima. Cada vez puedes subir1o2escalones. ¿Cuántos métodos diferentes hay para llegar a la cima?

Método 1: Recursión por fuerza bruta (ineficiente)

Según el análisis inicial, podemos escribir directamente la fórmula recursiva:f(n) = f(n-1) + f(n-2)donde,f(1) = 1, f(2) = 2。

Ejemplo

def climb_stairs_recursive(n: int) -> int:
    """Solución recursiva"""
    if n == 1:
        return 1
    if n == 2:
        return 2
    return climb_stairs_recursive(n - 1) + climb_stairs_recursive(n - 2)

# Prueba
print(f"Número de métodos para subir al escalón 5 (recursivo): {climb_stairs_recursive(5)}")  # Salida: 8

Análisis de desventajas: esta recursión conlleva una gran cantidad de cálculo repetido. Por ejemplo, calcularf(5)necesitaf(4)yf(3), calcularf(4)también necesitaf(3)yf(2), aquíf(3)se calcula dos veces. Cuandones muy grande, la complejidad temporal es exponencialO(2^n), extremadamente ineficiente.

Método 2: Recursión con memoización (de arriba hacia abajo)

Podemos usar un arreglo ("memo") para almacenar los resultados ya calculados y evitar cálculos repetidos.

Ejemplo

def climb_stairs_memo(n: int) -> int:
    """Recursión con memoización (de arriba hacia abajo)"""
    # Inicializar el memo, -1 indica no calculado
    memo = [-1] * (n + 1)
   
    def helper(x: int) -> int:
        # Caso base
        if x == 1:
            return 1
        if x == 2:
            return 2
        # Si ya se calculó, devolver el resultado directamente
        if memo[x] != -1:
            return memo[x]
        # De lo contrario, calcular y guardar en el memo
        memo[x] = helper(x - 1) + helper(x - 2)
        return memo[x]
   
    return helper(n)

print(f"Número de métodos para subir al escalón 5 (con memoización): {climb_stairs_memo(5)}")  # Salida: 8

La complejidad temporal de este método se reduce aO(n), porque cada subproblema se calcula solo una vez. La complejidad espacial esO(n). Esto ya es una idea de programación dinámica, llamada"de arriba hacia abajo"o"búsqueda con memoización"。

Método 3: Arreglo de recurrencia (de abajo hacia arriba, DP estándar)

Empezamos directamente desde el subproblema más pequeño, avanzando paso a paso hasta el problema original. Normalmente usamos un arreglodppara almacenar los estados.

Ejemplo

def climb_stairs_dp(n: int) -> int:
    """Programación dinámica (de abajo hacia arriba)"""
    if n <= 2:
        return n
    # 1. Definir el arreglo de estados: dp[i] representa el número de métodos para subir al i-ésimo escalón
    dp = [0] * (n + 1)
    # 2. Determinar las condiciones iniciales
    dp[1] = 1
    dp[2] = 2
    # 3. Transición de estados: recurrencia según la ecuación de transición de estados
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    # 4. Devolver el resultado final
    return dp[n]

print(f"Número de métodos para subir al escalón 5 (DP): {climb_stairs_dp(5)}")  # Salida: 8

Método 4: Optimización de espacio (arreglo deslizante)

Observando la ecuación de transición de estadosdp[i] = dp[i-1] + dp[i-2], descubrimos que el estado actual solo depende de los dos estados anteriores. Por lo tanto, no necesitamos guardar todo eldparreglo, solo necesitamos dos variables para actualizarlo de forma deslizante.

Ejemplo

def climb_stairs_optimized(n: int) -> int:
    """Programación dinámica (versión optimizada en espacio)"""
    if n <= 2:
        return n
    # Solo se usan dos variables para representar dp[i-1] y dp[i-2]
    prev, curr = 1, 2  # Corresponden a dp
    for i in range(3, n + 1):
        # Calcular el nuevo valor actual
        new_curr = prev + curr
        # Actualizar las variables de forma deslizante para preparar el siguiente ciclo
        prev, curr = curr, new_curr
    return curr

print(f"Número de métodos para subir al escalón 5 (DP optimizado): {climb_stairs_optimized(5)}")  # Salida: 8

Después de la optimización, la complejidad espacial se reduce deO(n)aO(1)。


Marco de resolución de problemas de programación dinámica

A través del problema de subir escaleras, podemos resumir el proceso universal de cuatro pasos para resolver problemas de programación dinámica:

Paso 1: Definir el estado

Usa uno o más arreglos (normalmente llamadosdp) para representar las soluciones de los subproblemas. La clave es entender quédp[i]odp[i][j]significan.

En el problema de subir escaleras, definimosdp[i]como «el número total de métodos para subir aliescalón».

Paso 2: Determinar la ecuación de transición de estados

Encontrar la relación entredp[i]y los estados anteriores (comodp[i-1], dp[i-2]) es el núcleo y la dificultad de la programación dinámica.

En el problema de subir escaleras, la ecuación de transición de estados es:dp[i] = dp[i-1] + dp[i-2]。

Paso 3: Determinar las condiciones iniciales (caso base)

Las soluciones de los subproblemas más pequeños e indivisibles. Este es el punto de partida de la recurrencia y debe definirse manualmente.

En el problema de subir escaleras, las condiciones iniciales son:dp[1] = 1, dp[2] = 2。

Paso 4: Determinar el orden de cálculo y calcular

Determinar si es "de arriba hacia abajo" (recursión con memoización) o "de abajo hacia arriba" (recurrencia con bucle), y asegurarse de que al calculardp[i], los subproblemas de los que depende ya hayan sido calculados.

En el problema de subir escaleras, usamos el enfoque de abajo hacia arriba, desdei=3hastai=n。


Caso clásico: Sucesión de Fibonacci

La sucesión de Fibonacci es el ejemplo más directo de programación dinámica; su propia definición es la ecuación de transición de estados.

Problema: calcular elntérmino de la sucesión de Fibonacci.F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) (n>=2)

Ejemplo

def fibonacci(n: int) -> int:
    """Programación dinámica para calcular números de Fibonacci"""
    if n < 2:
        return n
    # Escritura con optimización de espacio
    prev, curr = 0, 1  # F(0), F(1)
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

# Datos de prueba
test_n = 10
print(f"El término {test_n} de la sucesión de Fibonacci es: {fibonacci(test_n)}")  # Salida: 55

Caso avanzado: Cambio de monedas

Este es un problema más típico que muestra la subestructura óptima.

Descripción del problema: te dan un array de enteroscoins, que representa monedas de diferentes denominaciones, y un enteroamount, que representa la cantidad total. Calcula y devuelve el número mínimo de monedas necesario para formar la cantidad total. Si no hay ninguna combinación de monedas que pueda formar la cantidad total, devuelve-1. Puedes considerar que la cantidad de cada tipo de moneda es ilimitada.

Análisis del problema y diseño de DP

  1. Definición del estado:dp[i]que representa, para la cantidad totaliel número mínimo de monedas necesario.
  2. Ecuación de transición de estados: para la cantidadi, podemos recorrer cada denominación de monedacoin. Sicoin <= i, entonces una forma posible de formar la cantidadies: primero formar la cantidadi - coin, y luego añadir una moneda decoindenominación.dp[i] = min(dp[i], dp[i - coin] + 1), para todos los que cumplancoin <= idecoin。
  3. Condiciones iniciales:dp[0] = 0, formar la cantidad 0 requiere 0 monedas. Los demásdp[i]se inicializan a un número muy grande (comoamount + 1ofloat('inf')), que representa que temporalmente no se puede formar.
  4. Orden de cálculo: de abajo hacia arriba, desdei=1calculando hastai=amount。

Implementación del código

Ejemplo

def coin_change(coins: list, amount: int) -> int:
    """Cambio de monedas - Programación dinámica"""
    # Inicializar el array dp, donde dp[i] representa el número mínimo de monedas para la cantidad i
    # Establecer un valor inicial inalcanzable: amount + 1
    dp = [amount + 1] * (amount + 1)
    dp[0] = 0  # La cantidad 0 requiere 0 monedas
   
    # Bucle exterior: recorrer todos los estados de cantidad
    for i in range(1, amount + 1):
        # Bucle interior: recorrer todas las opciones de moneda
        for coin in coins:
            # Si la denominación de la moneda actual es menor o igual que la cantidad actual, se puede considerar usar esta moneda
            if coin <= i:
                # Transición de estado: dp[i] es el valor entre la solución que no usa la moneda actual y
                # la solución que usa la moneda actual (es decir, dp[i-coin] + 1), el menor de los dos.
                dp[i] = min(dp[i], dp[i - coin] + 1)
   
    # Si dp[amount] no se ha actualizado (sigue siendo el valor inicial), significa que no se puede formar
    return dp[amount] if dp[amount] <= amount else -1

# Datos de prueba
coins = [1, 2, 5]
amount = 11
print(f"El número mínimo de monedas necesario para formar la cantidad total {amount} es: {coin_change(coins, amount)}")  # Salida: 3 (5+5+1)

Ejercicios prácticos

Intenta resolver los siguientes problemas de forma independiente para consolidar tu comprensión de la programación dinámica:

Ejercicio 1: Suma máxima de subarreglo

Te dan un array de enterosnums, encuentra un subarreglo contiguo con la suma máxima y devuelve su suma máxima.

Ejemplo:

输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6。

Pista:

  • Definirdp[i]como 'la suma máxima del subarreglo contiguo que termina en eliésimo elemento'.
  • Ecuación de transición de estados:dp[i] = max(nums[i], dp[i-1] + nums[i])。
  • La respuesta final es el máximo entre todosdp[i].

Ejercicio 2: Subsecuencia creciente más larga

Te dan un array de enterosnums, encuentra la longitud de la subsecuencia estrictamente creciente más larga.

Ejemplo:

输入:nums = [10,9,2,5,3,7,101,18]
输出:4
解释:最长递增子序列是 [2,3,7,101],因此长度为 4。

Pista:

  • Definirdp[i]como 'la longitud de la subsecuencia creciente más larga que termina en eliésimo número'.
  • Para cadai, es necesario recorrerjdesde0llegari-1, sinums[i] > nums[j], entoncesdp[i] = max(dp[i], dp[j] + 1)。
  • Inicialmente, cadadp[i]es al menos 1 (solo se contiene a sí mismo).
Otras extensiones