**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

1 2 3 4 5 6 7 8 9 |
int naiveFibonacci(int n){ if(n == 0) return 0; if(n == 1) return 1; return naiveFibonacci(n-1) + naiveFibonacci(n-2); } |

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

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#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**

*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:

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.