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;
    }