Dynamic Programming

1. What is Dynamic Programming?

Dynamic Programming is a technique in computer programming that helps to efficiently solve a class of problems that have overlapping subproblems and optimal substructure property.

 

If any problem can be divided into subproblems, which in turn are divided into smaller subproblems, and if there are overlapping among these subproblems, then the solutions to these subproblems can be saved for future reference.

 

2. Fibonacci sequence

A fibonacci series is the sequence of numbers in which each number is the sum of the two preceding ones.

 

1. The first term is 0.
2. The second term is 1.
3. The third term is sum of 0(from step 1) and 1(from step 2), which is 1.
4. The fourth term is the sum of the third term (from step 3) and second term (from step 2).

Hence we have hte sequence 0, 1, 1, 2, 3. Here, we have used the results of the previous steps as shown below. This is called a dynamic programming approach.

1. F(0) = 0
2. F(1) = 1
3. F(2) = F(1) + F(0)
4. F(3) = F(2) + F(1)
5. F(4) = F(3) + F(2)

 

3. How Dynamic Programminbg Wroks

Dynamic programming works by storing the result of subproblems so that when their solutions are required, they are at hand and we do not need to recalculate them.

 

This techinique of storing the value of subproblems is called memorization. By saving the values in the array, we save time for computations of sub-problems we have already across.

 

Dynamic probramming by memorization is a top-down approach to dynamic programming. By reversing the direction in which the algorithm works. by starting from the base case and working toward the solution, we can also implement dynamic programming in a bottom-up manner.

 

def Fibonacci(n) : 
    if n < 0 : 
    	print("Incoreect input")
    elif n == 0 : 
    	return 0 
    elif n == 1 : 
        return 1 
    else : 
        return F(n-1) + F(n-2)

 

4. Recursion vs Dynamic Programming

Dynamic programming is motly applied to recursive algorithms. This is not a coincidence, most optimization problems require recursion and dynamic programming is used for optimization.

 

But not all problems that use recursion can use Dynamic Programming. Unless there is a presence of overlapping subproblems like in the fibnoacci sequence problem, a recursion can only reach the solution using a divide and conquer approach.

 

https://www.programiz.com/dsa/dynamic-programming

Dynamic Programming