Summary: In this tutorial, we will learn what dynamic programming is with the help of an example of Fibonacci Series solution using dynamic programming algorithm.

Introduction to Dynamic Programming

Dynamic programming is a way of solving a problem by breaking it down into a collection of subproblems.

We store the solution of subproblems for its reuse i.e. when required it can be reused instead of computing it again.

This approach of reusing the previously calculated results eliminates computing of repeated task, hence increasing the performance of the code in terms of the time complexity.

In short, Dynamic programming optimizes code for the better execution and performance of the program. It reduces the time complexity of the algorithm or program i.e. the method takes far less time than the method which does not take advantages of dynamic programming.

Example using Dynamic Programming

Consider the following naive recursive program which computes the nth Fibonacci number:

int  naiveFibonacci(int n){
    if(n == 0)
       return 0;

    if(n == 1)
        return 1;

   return naiveFibonacci(n-1) + naiveFibonacci(n-2);
}

In this program, on each recursive call, there will be a further two recursive calls (like the Divide and conquer method), so it may happen that the pre-calculated value will be again calculated which is purely an overhead.

Refer to the diagram below for a clear picture:

What is dynammic programming

f() is the recursive function for computing Fibonacci number.

Here f(1), f(2), & f(0) are being computed and used multiple times.

Instead, we can store them in the array when they are calculated for the first time and reuse them when the same value needs to be used again.

This approach of storing the calculated values or sub solution for later use is called memoization (not memorize).

Here is the example of how we can use the dynamic programming to simplify the program of Fibonacci number:

#include <iostream>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm> //Using for fill method
 
using namespace std;
 
class Fibonaaci{
public:
    int memoize[100]; //Change 100 to MAX number to test for higher values
 
    //Constructor
    Fibonaaci(){
        fill(memoize,memoize+100,-1); //Initializing each element to -1
        memoize[0] = 0;
        memoize[1] = 1;
    };
 
    //Dynamic program for fibonaacci number
    int fibonaaciDP(int n){
 
        if(memoize[n] != -1) return memoize[n];
        //Storing the value in the array (Memoizing)
        memoize[n] = fibonaaciDP(n-1) + fibonaaciDP(n-2);
 
        return memoize[n];
 
    }
 
    int  naiveFibonaacci(int n){
        if(n == 0)
           return 0;
 
        if(n == 1)
            return 1;
 
       return naiveFibonaacci(n-1) + naiveFibonaacci(n-2);
    }
};
 
int main()
{
    Fibonaaci f;
    printf("%d",f.fibonaaciDP(15));
}

Output:

Dynamic program

610 is the 15th Fibonacci number (Considering 0 as zero-th number :P).

By using this approach, we are basically implementing dynamic programming.

Here is the illustration of how the execution of the above program will be for 4th Fibonacci number:

Dynammic programming example

Here we are computing each subproblem only once.

It is clear that the total number of computations is less than the naive recursive approach.

To test out both approach, use a large value of N. You will notice the difference in time taken by each approach to give the final result.

Dynamic Programming vs Divide and Conquer

  • Overlapping subproblems -> Dynamic Programming
  • Non Overlapping subproblems -> Divide and Conquer method
  • Divide and conquer method is used when problems can be solved by combining optimal solutions to non-overlapping sub-problems. E.g Merge Sort, Quick Sort etc.
  • Whereas Dynamic programming is used in those problems which have the scope of computing similar subproblems again and again.

In this tutorial, we learned the concept of dynamic programming with an example. We learned how dynamic programming can make algorithms more time-efficient when there is a possibility of reusing the solution of the subproblems.

This Post Has One Comment

  1. saurav rajput

    the contents are really amazing.
    thanks to you.

Leave a Reply

two + 12 =