# Introduction To Dynamic Programming — Fibonacci Series

What is Dynamic Programming:

Dynamic pro­gram­ming is a tech­nique to solve the recur­sive prob­lems in more effi­cient man­ner. Many times in recur­sion we solve the sub-problems repeat­edly. In dynamic pro­gram­ming we store the solu­tion of these sub-problems so that we do not have to solve them again, this is called Mem­o­iza­tion.

Dynamic pro­gram­ming and mem­o­iza­tion works together. So Most of the prob­lems are solved with two com­po­nents of dynamic pro­gram­ming (DP)-

• Recur­sion — Solve the sub-problems recursively
• Mem­o­iza­tion — Store the solu­tion of these sub-problems so that we do not have to solve them again

Exam­ple:

Fibonacci Series : The cur­rent num­ber is the sum of pre­vi­ous two num­ber. If can be defined as

```Fibonacchi(N) = 0                                   for n=0

= 0                                                   for n=1

= Fibonacchi(N-1)+Finacchi(N-2)                     for n>1

```

Now we see the Recur­sion Solution :

Fibonac­chi Recursion

Now as you can see in the pic­ture above while you are cal­cu­lat­ing Fibonacci(4) you need Fibonacci(3) and Fibonacci(2), Now for Fibonacci(3), you need Fibonacci (2) and Fibonacci (1) but you notice you have cal­cu­lated Fibonacci(2) while cal­cu­lat­ing Fibonacci(4) and again cal­cu­lat­ing it. So we are solv­ing many sub-problems again and again.

Time Com­plex­ity:

T(n) = T(n-1) + T(n-2) + 1 = 2n = O(2n)

Use Dynamic Pro­gram­ming — Memoization:

Store the sub-problems result so that you don’t have to cal­cu­late again. So first check if solu­tion is already avail­able, if yes then use it else cal­cu­late and store it for future.

Time Com­plex­ity: O(n) , Space Com­plex­ity : O(n)

Two major prop­er­ties of Dynamic programming–

To decide whether prob­lem can be solved by apply­ing Dynamic pro­gram­ming we check for two prop­er­ties. If prob­lem has these two prop­er­ties then we can solve that prob­lem using Dynamic programming.

1. Over­lap­ping Sub-problems
2. Opti­mal Substructure.

Over­lap­ping Sub-problems:

Over­lap­ping sub-problems, as the name sug­gests the sub-problems needs to be solved again and again. In recur­sion we solve those prob­lems every time and in dynamic pro­gram­ming we solve these sub prob­lems only once and store it for future use. As we can see in the pic­ture below that we are solv­ing many sub-problems repeatedly.

Opti­mal Sub­struc­ture: If a prob­lem can be solved by using the solu­tions of the sub prob­lems then we say that prob­lem has a Opti­mal Sub­struc­ture Prop­erty.

Dynamic Pro­gram­ming Approaches:

• Bottom-Up
• Top-Down

Bottom-Up Approach:

Sup­pose we need to solve the prob­lem for N, We start solv­ing the prob­lem with the small­est pos­si­ble inputs and store it for future. Now as you cal­cu­late for the big­ger val­ues use the stored solu­tions (solu­tion for smaller problems).

Bottom-Up solu­tion for Fibonacci Series:

Top-Down Approach:

Break the prob­lem into sub-problems and solve them as needed and store the solu­tion for future.

#### You may also like...

• Arafath Ali

Sorry a novice ques­tion here, I think y code using recur­sion gets this done in o(n). Please cor­rect me :

pub­lic sta­tic int fibDP(int x) {

if(x==0)
return 0;

if(x==1)
return 1;
else{
int result = x*fibDP(x-1);
return result;
}

}

• tuto­ri­al­hori­zon

The code have writ­ten is for fac­to­r­ial or Fibonacci series? Becoz it does not looks like Fibonacci

• Arafath Ali

Ohh yea .. sorry my bad.

• The Utopian Malayali

How would you eval­u­ate this code:

``` private static long fib(long n) { if(n < 2) return 1; long fib1 = 0; long fib2 = 0; if(fibMap.containsKey(n-2)){ fib1 = fibMap.get(n-2); }else{ fib1 = fib(n-2); fibMap.put(n-2, fib1); } if(fibMap.containsKey(n-1)){ fib2 = fibMap.get(n-1); }else{ fib2 = fib(n-1); fibMap.put(n-1, fib2); }```

``` ```

``` return fib1+fib2; } ```

• Anushree Achar­jee

pub­lic sta­tic int fiboWithDP(int n){
int[] mem­ory = new int[n+1];
memory[0]= 0;
memory[1] = 1;
for(int i = 1; i < n + 1; i++){
memory[i] = memory[i — 1]+ memory[i — 2];
}
return memory[n];
}

gives Arrayin­dex­Out­Of­Bound Excp­tion at memory[1]=1. Why?

• Tạ Anh Tú

I love this web­site, it helps me a lot about algorithms!