Table of Contents

## 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
```

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

- Data Structure and Algorithms,
- Dynamic Programming – Wikipedia,
- What is the difference between bottom-up and top-down? – Stack Overflow Question.