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.