What is Dynamic Programming?

Dynamic Programming

Introduction

Today in this tutorial, we are going to discuss the concept of Dynamic Programming. It is a much more optimal approach to programming.


Dynamic Programming

Theoretically, Dynamic Programming is a problem-solving technique that solves a problem by dividing it into sub-problems. When the sub-problems are same and dependent, Dynamic programming comes into the picture.

It is very similar to the Divide and Conquer approach to problem-solving. But in some cases, the Divide and Conquer technique may perform some operations or tasks multiple times (increasing time complexity).

Hence, the Dynamic Programming method (DP) is normally used to optimize a specific problem.

Further, DP follows the Principle of Optimality which states that for an optimal sequence of decisions, each sub-sequence must also be optimal.


Example – Fibonacci Using DP

Now that we have discussed the basic concept of Dynamic Programming, let us look at how to solve a problem using this method.

In the example below, we try to calculate the number at the position n (user input) in the Fibonacci series.

As you know, a Fibonacci series looks like this,

0, 1, 1, 2, 3, 5, 8 … upto n terms.

Here, the starting two digits are 0 and 1.

Let’s write a program to automatically find the right number at a specific point in the Fibonacci sequence based on the user input.


Using Recursion(in C):

#include<stdio.h>
//fibonacci calculating function
int fibo(int n) 
{ 
	if(n==1)
		return 0;
	else if(n==2)
		return 1;
	else
		return fibo(n-1) + fibo(n-2); 
}
int main()
{
	int n,res;
	printf("Enter n : ");
	scanf("%d",&n);
	
	res=fibo(n);
	
	printf("fibo(%d) = %d",n,res);
	
	return 0;
}

Output:

Enter n : 5
fibo(5) = 3
Fibo2
Fibonacci using Recursion( if n=5 )

So as you can see, in our above example taking n=5, recursion breaks the problem into sub-problems using recursive calls.

Take a closer look, notice that in this case, fibo(3) is calculated twice. Which then breaks down to two recursive calls for fibo(1) and fibo(2). They have values 0 and 1 respectively. Finally, we get our desired output i.e., fibo(5) = 3.


Applying DP(in C):

#include<stdio.h>

int fibo_series[100]; 


void set_zero()  
{  
    int i;  
    for (i = 1; i <= 100; i++)  
        fibo_series[i] = 0; 
}  
//fibonacci calculating function
int fibo(int n)  
{  
    if (fibo_series[n] == 0)  
    {  
        if (n <= 1)
            fibo_series[n] = n;  
        else
            fibo_series[n] = fibo(n - 1) + fibo(n - 2);  
	}  
	return fibo_series[n];  
}   
int main ()  
{  
    int n,res;  
    set_zero(); 
    
    printf("Enter n : ");
	scanf("%d",&n);
	
	if(n>=100 || n<=0)
		printf("Entered number is out of range!");
	else
	{
		res=fibo(n-1);
		printf("fibo(%d) = %d",n,res);
	}
	
	return 0;  
}

Output:

Enter n : 5
fibo(5) = 3
  • This time firstly we initialize an array fibo_series[] with a maximum 100 elements to have a value 0, using the function set_zero(),
  • This array is further going to be used to store the Fibonacci series’s elements as soon as one is calculated,
  • Inside the fibo() function first, we check whether the required element has been already calculated and stored inside the array or not. If not, it is calculated. And if yes, the element is directly passed to the site of the function call,
  • This ensures that the same function(as we saw earlier fibo(3)) is not called twice. Hence in this way, we get the optimal solution.

Note: We pass (n-1) while calculating res to the function fibo() since the array index starts from zero. Whereas, we are considering the elements of the series to start with index 1.

For the same reason, we have used an if-else statement to eliminate the cases where the user enters n as n>=100 or n<=0.


Conclusion

So in this tutorial, we learned about the Dynamic Programming technique with its implementation and how it gives us an optimal solution.

For any further questions, feel free to use the comments below.


References

Leave a Reply

Your email address will not be published. Required fields are marked *

close
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages