Introduction to Dynamic Programming

Dynamic Programming is an algorithmic approach to solve some complex problems easily and save time and number of comparisons by storing the results of past computations. The basic idea of dynamic programming is to store the results of previous calculation and reuse it in future instead of recalculating them.

Consider a simple example of calculating Factorials from 1 to N.

The naive idea will be to run a loop from 1 to N and for each number, calculate the factorial and print it.

for(i = 1 to N)
{
    factorial = 1;

    for(j = 1 to i)
    {
        factorial = factorial * j;
    }
    
    print factorial;
}

If we observe carefully, we can see that factorial(N) = N*factorial(N-1). That is the factorial of the next number will be the factorial of the current number multiplied by the next number itself. So, we can store the previous calculations in an array and need not to calculate factorial every time for a new number.

This is one of the simplest dynamic programming problem:

// Empty array to store factorials
factorial[N] = {};

// Factorial of 0 and 1 is 1
factorial[0] = 1;
factorial[1] = 1;

for(i = 2 to N)
{
    // Factorial of current number is factorial 
    // of previous number multiplied by current number
    factorial[i] = factorial[i-1]*i;
}

We can also see Dynamic Programming as dividing a particular problem into subproblems and then storing the result of these subproblems to calculate the result of the actual problem.

Let us take another problem to understand this. Consider the problem to find the N-th Fibonacci number.

We know that n-th fibonacci number fib(n) can be defined as:

fib(n) = fib(n-1) + fib(n-2), where n >= 2.

and,

fib(0) = fib(1) = 1.

We can see that the above function fib() to find the nth fibonacci number is divided into two subproblems fib(n-1) and fib(n-2) each one of which will be further divided into subproblems and so on.

The first few Fibonacci numbers are:

1, 1, 2, 3, 5, 8, 13, 21, 34,……..

Below is the recursion tree for the recursive solution to find the N-th Fibonacci number:

                         fib(5)
                     /             \
               fib(4)                fib(3)
             /      \                /     \
         fib(3)      fib(2)         fib(2)    fib(1)
        /     \        /    \       /    \
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /    \
fib(1) fib(0)

We can see that the function fib(3) is being called 2 times. If we would have stored the value of fib(3), then instead of computing it again, we could have reused the old stored value.