Dynamic programming is a method of solving a complex problem by breaking it down into a collection of simpler problems. Dynamic programming is a way to optimize code for the better execution and performance of the program.

Using Dynamic programming in C++ program 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.

The basic concept of the dynamic programming is to store the solution of subproblem so that when required it can be reused instead of computing it again.

Dynamic Programming Example

Take an example as the recursive program to find the fibonacci number, the code would be:

Normal Fibonacci Program

By using this technique on each recursive call there will be a further two recursive call (somewhere like 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:

f() is the recursive function for computing Fibonacci

What is dynammic programming

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).

Dynamic Fibonacci program

Output

Dynamic program

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

And by using this approach basically, we are implementing dynamic programming. Thus by using dynamic programming to calculate Fibonacci number, our program execution will look like this:

Dynammic programming example

Here we are each subproblem only once and thus reducing the number of computation.

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.

Hope that you understood the concept of the dynamic programming. If you have any doubts then comment below.

Leave a Reply

Close Menu