Dynamic Programming

Sourav Saraf — Fri, 26 Feb 2021 05:09:22 +0000

Hello Folks,
In this blog we are trying to provide you a flavour of what actually Dynamic Programming is and how to use it.
To provide clear understanding we will be referring to a very common problem named Fibonacci Series with which we are well aware of.
There are multiple ways of solving the problem. They are:

Recursion
Top Down DP
Bottom Up DP
Space Optimised Approach.

We will be discussing each approach in details.

So, Let's Start!

1. Recursion

We know that in Recursion, a function calls itself multiple times till it hits the base case to solve a particular problem. If we initially try to understand how exactly is recursion working then it will be a problem and we may get confused and may not find a way to solve the problem. Initially we should be focusing on large problem and how it can be solved. Then we should define a function and tell it where to stop i.e specify the base case and write code to solve the larger problem and leave the rest in hands of recursion.
Like for the Fibonacci series we know that 1st term is 1 and nth term is sum of previous 2 terms i.e n-1 and n-2. So lets write that and leave the rest to recursion.

int fibonacci(int n)
{
    if(n==1 || n==0)
        return n;
    return fibonacci(n-1)+fibonacci(n-2);
}

The above function is going to work absolutely fine but is this an an optimal approach?

Lets try to understand it. Suppose using above function we are trying to find the 5th Fibonacci term. The above code will generate the following recursion tree.

We can see that recursion tree repeats for some elements a number of times (Highlighted in Red) i.e same work is done again and again. The number of repetition will be even more higher for large numbers. Also the above code has time complexity of O(2^n) which is exponential and is really very bad.

So the answer to above question is NO. This is not an optimal approach.

Nothing to worry about 😊. Dynamic Programming will sort it out.

So what's Dynamic Programming then?

A quote by Winston Churchill says:

Those who fail to learn from history are condemned to repeat it.

This is what Dynamic Programming does. We store the already calculated value so that it can be used as and when required and re-calculation can be avoided.

Let's Discuss them!

2. Top Down DP

When we start from large sub-problem and reach base case it is called Top Down DP Approach. In this approach we use Recursion + Memoization i.e calculate the value using recursion and store it in some array so that we don't have to re-calculate.
Lets see how can Fibonacci Series problem can be solved with this approach.

int dp[100]={0}; // I am assuming size to be 100. It can be anything
int fibonacci(int n)
{
    if(n==0||n==1)
        return n;
    if(dp[n]!=0)
        return dp[n]; //If the value has already been calculated, return it
    dp[n] = fibonacci(n-1)+fibonacci(n-2);
    return dp[n];
}

What do you say about the above code ? Far better then that of recursion (of course not in length :)).
So, the time complexity of above code is O(N) and Space Complexity of O(N) is also required.

3. Bottom Up DP

In this approach we start from base case and reach the required solution. No recursion is needed in this approach.

Have a look at the code.

int fibonacci(int n)
{
    int dp[100]={0}; // I am assuming size to be 100. It can be anything
    dp[1]=1; //We need to provide starting values
    for(int i=2;i<=n;i++)
    {
        dp[i]=dp[i-1]+dp[i-2];
    }
    return dp[n];
}

Time and Space Complexity remains the same as above i.e O(N).

I hope that the above explanation and code gave you some idea and flavour of what Dynamic Programming is and how it works. Don't worry. I have not forgotten the 4th section. Its not something very much related to DP so I will discuss it below 😊.

So from the above discussion we can conclude that DP highly optimised the code and saves computational resources like memory.
A huge amount of practice is required for achieving expertization in Dynamic Programming and having knowledge of other algorithms may also help in reaching an optimal DP Solution.

Now its time for Space Optimised approach.

4. Space Optimised Approach
This approach may not necessarily work for all problems as it works for Fibonacci Sequence. In this approach we can find the nth element even without using any array!

Have a look.

int fibonacci(int n)
{
    int a=0,b=1,c;
    for(int i=2;i<=n;i++)
    {
        c=a+b;
        a=b;
        b=c;
    }
    return c;
}

So, lets end our blog here.
Thanks to all the readers for their time. Any feedbacks are always welcome. Hope to see all of you in my upcoming blogs as well.
Thank You 😊.

DEV Community: Sourav Saraf

Dynamic Programming