Python | Implementación de programación dinámica usando Dictionary

La programación dinámica es una forma que se puede utilizar como una optimización sobre la recursividad simple . Dondequiera que veamos una solución recursiva que tiene llamadas repetidas para las mismas entradas, podemos optimizarla usando Programación Dinámica. La idea es simplemente almacenar los resultados de los subproblemas para que no tengamos que volver a calcularlos cuando sea necesario más adelante. Esta sencilla optimización reduce las complejidades del tiempo de exponencial a polinomial. En este artículo, se ha discutido  un método para usar los diccionarios de python para implementar la programación dinámica.

Para entender la implementación de la programación dinámica en python, visualicémosla usando el problema de los números de Fibonacci . 

En términos matemáticos, la secuencia de números de Fibonacci se define por la relación de recurrencia:  

Fn = Fn-1 + Fn-2

con valores semilla:  

F0 = 0 and F1 = 1

Ejemplos:  

Entrada: N = 9  Salida
: 34 
Explicación: El  ^noveno número en la serie de Fibonacci es 34.

Entrada: N = 2 
Salida: 1 
Explicación:  ^El
segundo número en la serie de Fibonacci es 1. 
 

A continuación se muestra la implementación del enfoque ingenuo: 

# Function to find nth Fibonacci number
def Fibonacci(n):
 
    # Corner case
    if n<0:
        print("Incorrect input")
 
    # Base case
    elif n == 0:
        return 0
    elif n == 1:
        return 1
 
    # Recursive case
    else:
        return Fibonacci(n-1)+Fibonacci(n-2)
   
print(Fibonacci(9))

34

Claramente, el enfoque anterior tiene una complejidad de tiempo exponencial. Para almacenar los resultados calculados previamente, usemos la clase de diccionario de python. 

Enfoque: La idea es personalizar el método __missing__ de la clase de diccionario. Este método se ejecuta cuando el usuario intenta acceder a una clave que no está en el diccionario. Usaremos nuestra propia definición de función para reescribir este método. 
A continuación se muestra la implementación del enfoque anterior:

# Python program to customize the
# __missing__ method of the
# dictionary class in python
 
class Fibonacci(dict):
 
    # Function signature of the
    # __missing__ function in
    # python
    def __missing__(self, n):
         
        # Base case
        if n<= 1:
 
            # Storing the value in the
            # dictionary before returning
            self[n] = n
            return n
 
        # Storing the value in the dictionary
        # before returning the value
        val = self[n] = self[n-1] + self[n-2]
        return val
 
if __name__ == "__main__":
 
    # Create an instance of the class
    Fib = Fibonacci()
    N = Fib[9]
    print(N)

34

El método anterior también se puede implementar usando un decorador en python. 
Decorator es una herramienta muy poderosa y útil en python ya que permite a los programadores modificar el comportamiento de una función o clase. Los decoradores nos permiten envolver otra función para extender el comportamiento de la función envuelta, sin modificarla permanentemente. Aquí, la memorización se utiliza para implementar un decorador. 

A continuación se muestra la implementación del enfoque anterior:

# Python program to find the nth Fibonacci
# number with memoization using decorators
 
from inspect import signature
 
# Defining a decorator
class memoize(dict):
 
    # Initializing function
    def __init__(self, func):
        self.func = func
        self.signature = signature(func)
 
    # Missing method to store the
    # Fibonacci numbers in a
    # Dictionary
    def __missing__(self, key):
        (arg, kwarg) = key
        self[key] = val = self.func(*arg, 
                          **dict(kwarg))
        return val
 
    def __call__(self, *arg, **kwarg):
        key = self.signature.bind(*arg,
                                  **kwarg)
        return self[key.args,
                    frozenset(key.kwargs.items())]
 
 
# Function to find the n-th Fibonacci
# number using the above defined
# decorator
@memoize
def Fibonacci(n):
 
    # Corner case
    if n<0:
        print("Incorrect input")
 
    # Base cases
    elif n == 0:
        return 0
    elif n == 1:
        return 1
 
    # Recursive case
    else:
        return Fibonacci(n-1)+Fibonacci(n-2)
 
if __name__ == "__main__":
    print(Fibonacci(9))

34