Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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 :

Fibonacchi Recursion

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.

Fibonacchi Recursion

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?

    • moe mufti

      Put i = 2, because you should start the posi­tion at index 2.
      You can see appar­ently index[0] and index[1] is already declared and initialized.

    • MGG

      since your for loop starts at i = 1, memory[i — 2] gives Arrayin­dex­Out­Of­Bound since 1 — 2 < 0

  • Tạ Anh Tú

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