Introduction to Dynamic Programming with Simple Explanation

byAnonymous -
0



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 Fn=Fn-1 + Fn-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(2n)
  • 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 Fn-2, Fn-3, ... , F2, F1 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 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 Fn and to find this we have calculated F1, F2, ... , Fn-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 Fn we first solve Fn-1, Fn-2, ... , F3, F2, F1 by using the recursion formula and base cases.
  • We know that F1 = F2 = 1 and Fn = Fn-1 + Fn-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
Tags:

Post a Comment

Previous Post Next Post