The dynamic programing approach seeks to solve each sub problem only once thus reducing the number of computations once the solution to a given subproblem has been computed, it is simply stored.
When the next time the same solution is needed, it is simply looked up.
The approach is especially useful when the number of repeating subproblems grows exponentially as a function of the size of the input
It follows the Principal of Optimality and Repeating Subproblem
Here are a few Examples for better understanding
Lets take a look at the problem of finding the Factorial of a number using recursion
What do you mean by factorial of a number ?
It is the product of all the integers from 1 to that number.
The symbol indicating Factorial is ‘!’ like 5! and 6!
For example: factorial of 5 is 1*2*3*4*5 = 120
And Factorial of 0 is 1What is Recursion?
A Recursion is self calling function with a appropiate terminating condition that follows a stack order.
For factorial 4 the graph looks like this,
We can notice that there are many different calls of the function with the exact same input value. In particular, Fib(2) was calculated 2 times!
# Factorial of a number using recursion
global steps
steps = 0
def recursion_factorial(n):
global steps
if n == 1:
steps+=1
return n
else:
steps += 1
return n*recursion_factorial(n-1)
#print(steps)
num = 7
# check if the number is negative
if num < 0:
print("Sorry, factorial does not exist for negative numbers")
elif num == 0:
print("The factorial of 0 is 1")
else:
print("The factorial of", num, "is", recursion_factorial(num), "in ",steps," steps")
steps =0
num = 8
# check if the number is negative
if num < 0:
print("Sorry, factorial does not exist for negative numbers")
elif num == 0:
print("The factorial of 0 is 1")
else:
print("The factorial of", num, "is", recursion_factorial(num), "in ",steps," steps")Output:
The factorial of 7 is 5040 in 7 steps
The factorial of 8 is 40320 in 8 stepsHere the Function def recursion_factorial(n) is called untill and unless n is equal to 1, thats when it is terminated.
At first when we call for 7! and it will run the program for 7 steps and return at the end step when it reaches 1
Then again, if we call for 8! it will take 8 steps to execute the program.
But,
We could have just extend one more step from the 7! to get 8! and it would have taken less time to compute, right?
Like,
7! = 1*2*3*4*5*6*7
8! = 1*2*3*4*5*6*7 * 8
so we could have written
8! = 7! * 8,
That would make sense too
Dynamic Programing solves this problem here.
storage={0:1,1:1}
global step
step=0
def DPfact(N):
global step
if N in storage:
#print(storage)
step=step+1
return storage[N]
else:
factorial=N*DPfact(N-1)
storage[N]=factorial
step=step+1
#print(storage)
return factorial
print("factorial of 5",end="=")
print(DPfact(5))
print("Total Steps: " , step)
print()
step = 0
#print(storage)
print("factorial of 10",end="=")
print(DPfact(10))
print("Total Steps: " , step)
print()
step = 0
#print(storage)
print("factorial of 20",end="=")
print(DPfact(20))
print("Total Steps: " , step)
print()Output:
factorial of 5=120
Total Steps: 5
factorial of 10=3628800
Total Steps: 6
factorial of 20=2432902008176640000
Total Steps: 11
Here storage stores the result for the previously entered values and all the results of the factorial and saves the time for the next iterations
Here, for the factorial of 10, it started after 5! because it has already been done previously, so it took extra 6 steps for finding 10! instead of 10 steps. One for checking and the rest 5 steps for calculating.
5! = 1*2*3*4*5 = 120
now, 10! = 1*2*3*4*5*6*7*8*9*10
or else, 10! = 5! * 6*7*8*9*10
or else, 10! = 120 * 6*7*8*9*10
That’s how Dynamic Programming optimizes the problem
Now,
We see Dynamic Programing for Fibonacci Series
What do you mean by fibonacci series ?
The Fibonacci series, named after Italian mathematician named Leonardo Pisano Bogollo, later known as Fibonacci, is a series (sum) formed by Fibonacci numbers denoted as Fn. The numbers in Fibonacci sequence are given as: 0, 1, 1, 2, 3, 5, 8, 13, 21, 38, . . .
First, lets us see Fibonacci Series using Normal Recursion
# Updated Fibonacci by Resursion
global step
step = 0
def fibonacci(n):
global step
f=[0,1]
for i in range(2,n+1):
f.append(f[i-1]+f[i-2])
step+=1
return f[:-1]
n=6
x=fibonacci(n)
for i in x:
print(i,end=", ")
print("Steps for fibo(6):",step-1)
step = 0
n=10
x=fibonacci(n)
for i in x:
print(i,end=", ")
print("Steps for fibo(10):",step-1)Output:
0, 1, 1, 2, 3, 5, Steps for fibo(6): 4
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, Steps for fibo(10): 8
For a normal Fibonacci series Fib(6) using recursion this type of graph is created
We can notice that there are many different calls of the function with the exact same input value. In particular, Fib(2) was calculated 5 times.
So to avoid this re-calculation we use dynamic programing as we are willing to trade memory in place of huge time complexity
# Fibonacci by Dynamic Programing
storage={0:0,1:1}
keys=[0,1]
global step
step = 0
def fibo(n):
global step
global step
if n-1 in storage:
return storage[n-1]
else:
for i in range (max(keys)+1,n):
keys.append(i)
storage[max(keys)]=storage[max(keys)-1]+storage[max(keys)-2]
step+=1
return list(storage.values())
print(fibo(6))
print("Steps for fibo(6) is:",step)
step = 0
print(fibo(10))
print("Steps for fibo(10) is:",step)Output:
[0, 1, 1, 2, 3, 5]
Steps for fibo(6) is: 4
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
Steps for fibo(10) is: 4Here the steps required for calculating fibo(10) after fibo(6) is only 4, thus reducing the step from 8 to 4. Isn’t it cool?
This is the reason we use Dynamic Programing.
~All the best
