Dynamic Programming (DP) is a general and powerful algorithm design technique intended for Optimization Problems like Maximization, Minimization, Shortest Path, etc.

Okay, that’s the broad view of Dynamic Programming. In a simple sentence, we can call Dynamic Programming is a careful implementation of the Brute force algorithm.

**Dynamic Programming ≈ Careful Brute Force Algorithm**

**Basic Idea: **What we want to do is take out the problem and somehow break it down into a reasonable number of subproblems in such a way that we can use optimal solutions to the smaller subproblems to give us optimal solutions to the larger ones.

This gives us a new formulation of **Dynamic Programming**.

**Dynamic Programming ≈ Subproblem + Reuse**

( Reuse the previous solution to get the solution of original Problem )

Let us understand this through an example,

**Example 1: Calculating Nth Fibonacci Number F**_{n}=F_{n-1} + F_{n-2}, where for n<=2 , Fn=1

_{n}=F

_{n-1}+ F

_{n-2}, where for n<=2 , Fn=1

**Method 1: Naive Approach**

- Our naive approach is to build a recursive function and then find the Nth Fibonacci like this

`int naiveFibonacci(int `*n*){
if(n<=2) return 1;
else return naiveFibonacci(n–1)+naiveFibonacci(n–2);
}

- The recurrence relation of this Algorithm is T(n) = T(n-1) + T(n-2) + O(1)
- Which on solving gives O(2
^{n}) - So these algorithms take an Exponential Time, now the question arises that can we make it better, the answer is
**“YES”**.

**Method 2: Memo(r)ization Table ( Top-Down ) Approach**

- The concept here is to store the previously calculated value and when we are going to calculate it again use that calculated value instead of computing it from the beginning. So what we store here, let us discuss this with the following tree for calculating Fibonacci Number.

- Now if we look into the recursive function tree build for finding
**Nth**Fibonacci Number then we observe that we are calculating the same value multiple times, instead, we can use the previously calculated value like this.

`int memoFibonacci(int `*n*, int *memo*[] ){
if N is calculated previously then return memo[N];
if(n<=2) return 1;
else nextTerm = memoFibonacci(n–1)+memoFibonacci(n–2);
memo[N] = nextTerm
return nextTerm
}

- This is particularly an efficient algorithm because of ones if we calculate F
_{n-2}, F_{n-3}, … , F_{2}, F_{1}in left subtree then in right that subtree will not be forming as we have already calculated value for it and we can use it from**memo table**. - I.e.
**memoFibonacci(k)**only recurse for the first time for all**k**. And after that, we use the value from**memo table**.

**Time Complexity**- Cost of each memo(r)ized calls = O(1).
- Non-memo(r)ized calls n, these are memoFibonacci(1), memoFibonacci(2), … , memoFibonacci(n)
- Cost of each non-recursive/ memo(r)ized calls = O(1)
- So overall time complexity is
**O(n)**

- Now from this, we will get a new approach to
**DP**- Memorize and reuse solutions to subproblems that help us to solve problems
**Dynamic Programming ≈ Memoization + Recursion**- As in the above case we need to find F
_{n}and to find this we have calculated F_{1}, F_{2}, … , F_{n-1}which are subproblems. **Time Complexity = No. of Subproblems * Cost/ Subproblems**- In cost/subproblems, we don’t count the cost of recursion as it is just called ones and the value we are using from the memo table which takes constant time.
- Therefore in the above example
- No. of subproblem = n.
- Cost/ subproblem = O(1)
- Total Cost = O(n)

**Method 3: Memo(r)ization Table ( Bottom-Up )Approach**

- In bottom to up approach to solve for F
_{n}we first solve F_{n-1}, F_{n-2}, … , F_{3}, F_{2}, F_{1}by using the recursion formula and base cases. - We know that F
_{1}= F_{2}= 1 and F_{n}= F_{n-1}+ F_{n-2}i.e. sum of two previous terms. - Time complexity =
**O(n)**

**Implementation of Method 3**

```
#include<bits/stdc++.h>
using namespace std;
int main(){
int n; cin>>n;
int fib[n+1];
fib[0]=0; fib[1]=1; fib[2]=1;
for(int i=3; i<=n; i++) fib[i]=fib[i–1]+fib[i–2];
cout<<“The “<<n<<“th fibonacci is: “<<fib[n]<<“n“;
}
```

**Input:**

`8`

**Output:**

`The Nth fibonacci is: 21`

**Practice Problems**

**Summary:**

In simple words, **Dynamic Programming** is nothing more than an abstract word for **“Memoization + Recursion”**.

In the next article, we will look into the steps involved in solving **Dynamic Programming Problems**.

If you have some **content OR material** related to this **OR there is an error** then do share them through the comment section for which we will be thankful to you.

Thank You