Dynamic Programming approach explained with simple example

Dynamic Programming is a programming technique which is used for solving complex problems by breaking it into comparatively simpler subproblems and finding the optimal solutions of the complex problems by finding the optimal solutions of these subproblems.

Even though, the name “Dynamic Programming” might scare people but actually its kind of simple if we follow some basic techniques to approach any complex problem.

Steps to tackle a problem using Dynamic Programming approach:

1) Define smaller problems from the original complex problems.

2) Solve these smaller problems using recursion.

3) Use smaller problems results to solve the bigger complex problem.

If you feel how come these simple steps will help solving a problem using DP approach then hang on and see for yourself how these simple looking steps will help solving complex problem effectively and efficiently.

Let’s have a look at a very simple Fibonacci program and use DP approach to optimize the program to make it faster using above simple steps.

Step 1) Define subproblem

For finding fibonacci number at “nth” place we need to know the “(n-1)th” and “(n-2)th” place number as we know,

Fib(n) = Fib(n-1) + Fib(n-2);

we can consider this as our smaller subproblem.

Step 2) Solve subproblem using recursion

A simple fibonacci function using recursion would be like as follows:

int FibonacciUsingRecursion(int number)
{
    if(number <= 2)
        return 1;
    else
        return (FibonacciUsingRecursion(number - 1) + FibonacciUsingRecursion(number - 2));
}

Step 3) Use smaller problems results to solve the bigger complex problem.

For saving small subproblem results (fibonacci values) we can define an array, and optimize the above recursive function to get the value from this array as follows:

#define MAX_FIB_PLACES 2000
int fib[MAX_FIB_PLACES];

// This function will calculate all the fibonacci values upto 1999 places (max limit of our problem).
// This is just a small function which is not fully optimized.

void initFib()
{
    fib[0] = 0;
    fib[1] = 1;
    fib[2] = 1;
    for (int i = 3; i < MAX_FIB_PLACES; i++)
    {
        fib[i] = fib[i – 1] + fib[i – 2];
    }
}

Now let’s compare the result in terms of execution time for both approach by calculating four different fibonnaci numbers:

#include <unistd.h>
#include <chrono>
#include <iostream>

using namespace std;
using namespace std::chrono;

#define MAX_FIB_PLACES 2000
int FibonacciUsingRecursion(int number)
{
    if(number <= 2)
        return 1;
    else
        return (FibonacciUsingRecursion(number - 1) + FibonacciUsingRecursion(number - 2));
}

int fib[MAX_FIB_PLACES];

// Calculating and storing all the fibonacci values
void initFib()
{
    fib[0] = 0;
    fib[1] = 1;
    fib[2] = 1;

    for (int i = 3; i < MAX_FIB_PLACES; i++)
    {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
}

int main()
{
    // Starting the timer
    high_resolution_clock::time_point t1 = high_resolution_clock::now();
    cout<<"Inside Fibonacci main using recursion "<<FibonacciUsingRecursion(4)<<endl;
    cout<<"Inside Fibonacci main using recursion "<<FibonacciUsingRecursion(10)<<endl;
    cout<<"Inside Fibonacci main using recursion "<<FibonacciUsingRecursion(20)<<endl;
    cout<<"Inside Fibonacci main using recursion "<<FibonacciUsingRecursion(40)<<endl;

    // Stopping the timer
    high_resolution_clock::time_point t2 = high_resolution_clock::now();

    // Starting the timer
    high_resolution_clock::time_point t3 = high_resolution_clock::now();
    initFib();
    cout<<"Inside Fibonacci main using Dynamic Programming "<<fib[4]<<endl;
    cout<<"Inside Fibonacci main using Dynamic Programming "<<fib[10]<<endl;
    cout<<"Inside Fibonacci main using Dynamic Programming "<<fib[20]<<endl;
    cout<<"Inside Fibonacci main using Dynamic Programming "<<fib[40]<<endl;
    // Stopping the timer
    high_resolution_clock::time_point t4 = high_resolution_clock::now();

    // Calculating execution time in both the approaches
    auto recDuration = duration_cast<microseconds>( t2 - t1 ).count();
    auto dpDuration = duration_cast<microseconds>( t4 - t3 ).count();

    cout<<"Calculation of Four fibonacci took "<<recDuration<<" microseconds using recursion"<<endl;
    cout<<"Calculation of Four fibonacci took "<<dpDuration<<" microseconds using DP"<<endl;

    return 0;
}

Let’s take a pause and take a guess about How much faster DP approach would be compared to recursion ?

Ready for the results ?

Here it is

Inside Fibonacci main using recursion 3
Inside Fibonacci main using recursion 55
Inside Fibonacci main using recursion 6765
Inside Fibonacci main using recursion 102334155
Inside Fibonacci main using Dynamic Programming 3
Inside Fibonacci main using Dynamic Programming 55
Inside Fibonacci main using Dynamic Programming 6765
Inside Fibonacci main using Dynamic Programming 102334155
Calculation of Four fibonacci took 667951 microseconds using recursion
Calculation of Four fibonacci took 21 microseconds using DP

DP approach is super fast compared to recursion and the best part is, all the fibonacci numbers are always available in the program.