Python | Implementing Dynamic programming using Dictionary
Last Updated :
09 Jul, 2021
Dynamic Programming is one way which can be used as an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for the same inputs, we can optimize it using Dynamic Programming. The idea is to simply store the results of subproblems so that we do not have to re-compute them when needed later. This simple optimization reduces time complexities from exponential to polynomial. In this article, a method to use dictionaries of python to implement dynamic programming has been discussed.
In order to understand the implementation of the dynamic programming in python, lets visualize it using the Fibonacci numbers problem.
In mathematical terms, the sequence of Fibonacci numbers is defined by the recurrence relation:
Fn = Fn-1 + Fn-2
with seed values:
F0 = 0 and F1 = 1
Examples:
Input: N = 9
Output: 34
Explanation:
9th number in the Fibonacci series is 34.
Input: N = 2
Output: 1
Explanation:
2nd number in the Fibonacci series is 1.
Below is the implementation of the naive approach:
Python3
# 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))
Clearly, the above approach has exponential time complexity. In order to store the previously computed results, let us use the dictionary class of python.
Approach: The idea is to customize the __missing__ method of the dictionary class. This method is executed when the user tries to access a key which is not in the dictionary. We will use our own function definition to rewrite this method.
Below is the implementation of the above approach:
Python3
# 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)
The above method can also be implemented by using a decorator in python.
Decorator is a very powerful and useful tool in python since it allows programmers to modify the behavior of function or class. Decorators allow us to wrap another function in order to extend the behavior of the wrapped function, without permanently modifying it. Here, memoization is used to implement a decorator.
Below is the implementation of the above approach:
Python3
# 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))
Similar Reads
Python 3.6 Dictionary Implementation using Hash Tables Dictionary in Python is a collection of data values, used to store data values like a map, which, unlike other Data Types that hold only a single value as an element, Dictionary holds key:value pair. Key-value is provided in the dictionary to make it more optimized. Each key-value pair in a Dictiona
3 min read
Dynamic Programming in Python Dynamic Programming is a commonly used algorithmic technique used to optimize recursive solutions when same subproblems are called again.The core idea behind DP is to store solutions to subproblems so that each is solved only once.To solve DP problems, we first write a recursive solution in a way th
7 min read
Output of python program | Set 14 (Dictionary) Prerequisite: Dictionary Note: Output of all these programs is tested on Python31) What is the output of the following program? PYTHON3 D = dict() for x in enumerate(range(2)): D[x[0]] = x[1] D[x[1]+7] = x[0] print(D) a) KeyError b) {0: 1, 7: 0, 1: 1, 8: 0} c) {0: 0, 7: 0, 1: 1, 8: 1} d) {1: 1, 7: 2
3 min read
How to implement Dictionary with Python3? This program uses python's container called dictionary (in dictionary a key is associated with some information). This program will take a word as input and returns the meaning of that word. Python3 should be installed in your system. If it not installed, install it from this link. Always try to ins
3 min read
Return Dictionary from a Function in Python Returning a dictionary from a function allows us to bundle multiple related data elements and pass them back easily. In this article, we will explore different ways to return dictionaries from functions in Python.The simplest approach to returning a dictionary from a function is to construct it dire
3 min read
How to Add Function in Python Dictionary Dictionaries in Python are strong, adaptable data structures that support key-value pair storage. Because of this property, dictionaries are a necessary tool for many kinds of programming jobs. Adding functions as values to dictionaries is an intriguing and sophisticated use case. This article looks
4 min read
Few mistakes when using Python dictionary Usually, A dictionary is a collection which is unordered, changeable and indexed. In Python, dictionaries are written with curly brackets, and they have keys and values. Each key-value pair in a Dictionary is separated by a 'colon', whereas each key is separated by a ‘comma’. Python3 1== my_dict = {
3 min read
Interesting Facts About Python Dictionary Python dictionaries are one of the most versatile and powerful built-in data structures in Python. They allow us to store and manage data in a key-value format, making them incredibly useful for handling a variety of tasks, from simple lookups to complex data manipulation. There are some interesting
7 min read
Iterate over a dictionary in Python In this article, we will cover How to Iterate Through a Dictionary in Python. To Loop through values in a dictionary you can use built-in methods like values(), items() or even directly iterate over the dictionary to access values with keys.How to Loop Through a Dictionary in PythonThere are multipl
6 min read