Introduction To Dynamic Programming – Fibonacci Series

What is Dynamic Programming:

Dynamic programming is a technique to solve the recursive problems in more efficient manner. Many times in recursion we solve the sub-problems repeatedly. In dynamic programming we store the solution of these sub-problems so that we do not have to solve them again, this is called Memoization.

Dynamic programming and memoization works together. So Most of the problems are solved with two components of dynamic programming (DP)-

  • Recursion – Solve the sub-problems recursively
  • Memoization – Store the solution of these sub-problems so that we do not have to solve them again

Example:

Fibonacci Series : The current number is the sum of previous two number. 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 Recursion Solution :

Fibonacchi Recursion

Fibonacchi Recursion

Now as you can see in the picture above while you are calculating 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 calculated Fibonacci(2) while calculating Fibonacci(4) and again calculating it. So we are solving many sub-problems again and again.

Time Complexity:

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

Use Dynamic Programming – Memoization:

Store the sub-problems result so that you don’t have to calculate again. So first check if solution is already available, if yes then use it else calculate and store it for future.

Time Complexity: O(n) , Space Complexity : O(n)

Two major properties of Dynamic programming-

To decide whether problem can be solved by applying Dynamic programming we check for two properties. If problem has these two properties then we can solve that problem using Dynamic programming.

  1. Overlapping Sub-problems
  2. Optimal Substructure.

Overlapping Sub-problems:

Overlapping sub-problems, as the name suggests the sub-problems needs to be solved again and again. In recursion we solve those problems every time and in dynamic programming we solve these sub problems only once and store it for future use. As we can see in the picture below that we are solving many sub-problems repeatedly.

Fibonacchi Recursion

Optimal Substructure: If a problem can be solved by using the solutions of the sub problems then we say that problem has a Optimal Substructure Property.

Dynamic Programming Approaches:

  • Bottom-Up
  • Top-Down

Bottom-Up Approach:

Suppose we need to solve the problem for N, We start solving the problem with the smallest possible inputs and store it for future. Now as you calculate for the bigger values use the stored solutions (solution for smaller problems).

Bottom-Up solution for Fibonacci Series:


Top-Down Approach:

Break the problem into sub-problems and solve them as needed and store the solution for future.

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

  • Arafath Ali

    Sorry a novice question here, I think y code using recursion gets this done in o(n). Please correct me :

    public static int fibDP(int x) {

    if(x==0)
    return 0;

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

    }

    • tutorialhorizon

      The code have written is for factorial or Fibonacci series? Becoz it does not looks like Fibonacci

      • Arafath Ali

        Ohh yea .. sorry my bad.

  • The Utopian Malayali

    How would you evaluate 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;
    }

    • Santosh Tripathi

      It should be described as Linked Hash Map then its correct .But then also it can give Fibonacci for n+1…only..

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

      return fib1+fib2;
      }

  • Anushree Acharjee

    public static int fiboWithDP(int n){
    int[] memory = 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 ArrayindexOutOfBound Excption at memory[1]=1. Why?

    • moe mufti

      Put i = 2, because you should start the position at index 2.
      You can see apparently index[0] and index[1] is already declared and initialized.

    • MGG

      since your for loop starts at i = 1, memory[i – 2] gives ArrayindexOutOfBound since 1 – 2 < 0

  • Tạ Anh Tú

    I love this website, it helps me a lot about algorithms!

  • Riaz Khan

    I really liked it . Precisely explained …….

%d bloggers like this: