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 una
nescalera 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 (el
nnivel) al empezar a pensar, puede parecer complicado.Pero si cambiamos de enfoque:Para llegar al
nescaló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:
- Subproblemas superpuestos: durante el proceso de resolución recursiva, el mismo subproblema se calcula múltiples veces.
- 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
"""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
"""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
"""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
"""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, definimos
dp[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, desde
i=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
"""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
- Definición del estado:
dp[i]que representa, para la cantidad totaliel número mínimo de monedas necesario. - Ecuación de transición de estados: para la cantidad
i, 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。 - 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. - Orden de cálculo: de abajo hacia arriba, desde
i=1calculando hastai=amount。
Implementación del código
Ejemplo
"""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:
- Definir
dp[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 todos
dp[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:
- Definir
dp[i]como 'la longitud de la subsecuencia creciente más larga que termina en eliésimo número'. - Para cada
i, es necesario recorrerjdesde0llegari-1, sinums[i] > nums[j], entoncesdp[i] = max(dp[i], dp[j] + 1)。 - Inicialmente, cada
dp[i]es al menos 1 (solo se contiene a sí mismo).
