Algoritmo de programación dinámica de Python
En el algoritmo de programación dinámica, los problemas complejos se descomponen recursivamente en subproblemas y los problemas complejos se resuelven resolviendo estos subproblemas. En comparación con los algoritmos recursivos, la programación dinámica reduce el uso de pilas, evita cálculos repetidos y mejora significativamente la eficiencia.
Veamos primero un ejemplo sencillo, la secuencia de Fibonacci.
La definición de secuencia de Fibonacci es la siguiente.
La secuencia de Fibonacci se puede implementar fácilmente usando un algoritmo recursivo:
Para el código anterior, a medida que n aumenta, la cantidad de cálculo aumenta exponencialmente y la complejidad temporal del algoritmo es .
Utilizando un algoritmo de programación dinámica, al calcular el valor de la secuencia de abajo hacia arriba, la complejidad del algoritmo se puede reducir a.
Veamos un ejemplo más complejo.
Este es un problema común con las monedas en la Olimpiada de Matemáticas de la escuela primaria: se sabe que hay tres tipos de monedas: 1 centavo, 2 centavos y 5 centavos. El número de monedas no está limitado. Las monedas se usan para hacer n centavos, entonces, ¿cuántos centavos hay?
Definimos los tipos de monedas usando la lista monedas
Definimos el problema como una matriz bidimensional dp, dp
dp forma una combinación cuya suma; es el número 5.
Para todos los dp[0][j], solo hay una situación en la que el precio total es 0, es decir, el número de todas las monedas es 0. Entonces, para cualquier j en el rango válido, dp[0][j] es 1.
Para el cálculo de dp[amt][j], es decir, utilizando el número de combinaciones de monedas[0:j 1] precio total de la moneda amt, se incluyen dos situaciones de cálculo:
1. Cuando se usa la j-ésima moneda, existe una situación de dp[amt-coins[j]][j], es decir, amt menos el valor de la j-ésima moneda y el número de combinaciones de las primeras j monedas se usa;
2. Cuando no se usa la j-ésima moneda, hay situaciones dp [amt] [j-1], es decir, las primeras j monedas se usan para formar el número de combinaciones de amt. ;
Entonces: dp[ amt][j] = dp[amt - coins[j]][j] dp[amt][j-1]
El resultado final es get es: dp[amount][-1]
El análisis anterior omite algunos casos extremos.
Con el análisis anterior, la implementación del código es relativamente simple.
El algoritmo de programación dinámica tiene código simple y alta eficiencia de ejecución. Pero en comparación con los algoritmos recursivos, se debe considerar cuidadosamente cómo descomponer el problema, y el código de programación dinámica es más difícil de entender que las llamadas recursivas.
También adjunto el código para la implementación del algoritmo recursivo a continuación. Los amigos interesados pueden comparar la complejidad temporal de los dos algoritmos.
El código anterior se ejecuta correctamente en Python 3.7.