Dynamic Programming

“Those who can't remember the past are condemned to repeat it” -Dynamic Programming.

What is dynamic programming?

The dynamic programming approach is similar to divide and conquer in breaking down the problem into smaller and yet smaller possible sub-problems. But unlike, divide and conquer, these sub-problems are not solved independently. Rather, results of these smaller sub-problems are remembered and used for similar or overlapping sub-problems.

Dynamic programming is used where we have problems, which can be divided into similar sub-problems so that their results can be re-used. Mostly, these algorithms are used for optimization. Before solving the in-hand sub-problem, the dynamic algorithm will try to examine the results of the previously solved sub-problems. The solutions of sub-problems are combined in order to achieve the best solution.

So we can say that −

• The problem should be able to be divided into smaller overlapping sub-problem.
• An optimum solution can be achieved by using an optimum solution of smaller sub-problems.
• Dynamic algorithms use Memoization/Tabulation.

There are mainly two different ways to solve problems/questions that are related to Dynamic Programming. They are -

• Memoization
• Tabulation

Memoization ensures that a method doesn’t run for the same inputs more than once by keeping a record of the results for the given inputs (usually in a hash map). Memoization basically optimizes the code or program that we have written. Let me explain this with a famous example (Fibonacci Numbers)

Program to print nth Fibonacci number without using memoization

//Fibonacci Series using Recursion
#include <bits/stdc++.h>
using namespace std;
int fib(int n)
{    if (n <= 1)
        return n;
    return fib(n-1) + fib(n-2);
} 
int main ()
{    
    int n;
    cin>>n;
    cout << fib(n);
    return 0;
}

This is the recursive tree of the above program with the input value of 6

Time Complexity: T(n) = T(n-1) + T(n-2) which is exponential.

Extra Space: O(n) if we consider the function call stack size, otherwise O(1).

We can observe that this implementation does a lot of repeated work (see the recursion tree). So this is a bad implementation for the nth Fibonacci number. so by using memoization we store the value that we have done in the past and without calling the function we directly return the value that we have stored

Program to print nth Fibonacci number using memoization

#include <bits/stdc++.h>
int fibonacci(int n, std::map<int, int> values)
{  
   //base condition when n is equal to 0 or 1
   if (n==0 || n==1)    
        return n;
   //checking whether the n value is present in map or not  
   std::map<int,int>::iterator iter = values.find(n); 
   //if m value is not present then call the respective functions
   if (iter == values.end())  
   { 
     //the nvalue is not present so we are using the fibonacci             //formula and calling the respective functions
     return values[n] = fibonacci(n-1) + fibonacci(n-2);  
   }  
   else  
   {  
      //returning the value that is already present without calling  //the function again
      return iter->second;  
   }
}
int main ()
{    
    int n;
    cin>>n;
    map<int,int> m;
    cout << fibonacci(n,m);
    return 0;
}

So let us now see how the recursive tree looks like when we use the memoized code

Time Complexity:O(n)
Extra Space: O(n)

As you can clearly see that using memoization we have decreased the number of function calls which implies that now our code is faster and optimized. Using Memoization we have reduced the complexity of the code from exponential to linear

Tabulation

With bottom-up, or tabulation, we start with the smallest problems and use the returned values to calculate larger values. We can think of it as entering values in a table, or spreadsheet, and then applying a formula to those values.

The time complexities and the space complexities for the two procedures tabulation and memoization are almost the same and in some cases it is exact. So now look into the Fibonacci example using tabulation

In the bottom-up dynamic programming approach, we’ll reorganize the order in which we solve the subproblems. or in other words

Start computing result for the subproblem. Using the subproblem result solve another subproblem and finally solve the whole problem

We’ll compute, F(0) then F(1), then, F(2), and so on:

This will allow us to compute the solution to each problem only once, and we’ll only need to save two intermediate results at a time.

For example, when we’re trying to find F(2), we only need to have the solutions to F(1) and F(0) available. Similarly, for F(3), we only need to have the solutions to F(2) and F(1).

This will allow us to use less memory space in our code.

#include<stdio.h>

int Fibonacci(int N)
{
    //if N = 2, we need to store 3 fibonacci members(0,1,1)
    //if N = 3, we need to store 4 fibonacci members(0,1,1,2)
    //In general to compute Fib(N), we need N+1 size array.
    int Fib[N+1],i;

    //we know Fib[0] = 0, Fib[1]=1
    Fib[0] = 0;
    Fib[1] = 1;

    for(i = 2; i <= N; i++)
        Fib[i] = Fib[i-1]+Fib[i-2];

    //last index will have the result
    return Fib[N];
}

int main()
{
    int n;
    scanf("%d",&n);

    //if n == 0 or n == 1 the result is n
    if(n <= 1)
        printf("Fib(%d) = %d\n",n,n);
    else
        printf("Fib(%d) = %d\n",n,Fibonacci(n));

    return 0;
}

Now its time to find which method is better between memoization and tabulation by knowing the differences between them and analyzing them

Tabulation

• State Transition relation is difficult to think
• Code gets complicated when a lot of conditions are required
• Fast, as we directly access previous states from the table
• If all subproblems must be solved at least once, a bottom-up dynamic- programming algorithm usually outperforms a top-down memoized algorithm by a constant factor
• In the Tabulated version, starting from the first entry, all entries are filled one by one

Memoization

• State transition relation is easy to think
• Code is easy and less complicated
• Slow due to a lot of recursive calls and return statements
• If some subproblems in the subproblem space need not be solved at all, the memoized solution has the advantage of solving only those subproblems that are definitely required
• Unlike the Tabulated version, all entries of the lookup table are not necessarily filled in Memoized version

(Comparision for better understanding)

We can conclude that in some cases memoization is better whereas in some other cases tabulation method is better but in my experience, I have seen many people preferring the tabulation method over the memoization method

Dynamic Programming questions are often given in many top MNCs so it is a very good skill to have in your arsenal

Most of the dynamic programming questions are of the types given below and the numbers that are in the brackets are the models which are based on the title itself

Conclusion

Most of the problems you’ll face within Dynamic Programming already exist in one form or another. So the more you practice dynamic programming the much better you will be at solving them.

Thanks for reading.

Happy Coding 😄