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:

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:

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

five × 5 =