Dynamic Programming: An Overview and Implementation

Dynamic programming is an algorithmic approach to solve complex problems in optimal way. Basically, a complex problem is divided into multiple simpler sub-problems that are easier to solve and final solution depends on the solutions of all sub-problems.

Dynamic programming problems involve recursive patterns where solution is build up from the very base case to all the way up to the top. Therefore, it’s pretty intensive in term of time and space complexity. But there are few techniques which people use to optimize their solution so their algorithms take less time and memory to execute. Most popular ones are:

• Memoization
• Tabulation

Memoization:

Lot of sub-problems are repetitive but solved again because of the nature of the recursive algorithms. For example, consider the following Fibonacci sequence:

0, 1, 1, 2, 3, 5, 8, 13, …

We know that every Fib(n) in sequence is equal to Fib(n-1)+Fib(n-2). Let’s look at the code and its tree structure:

const Fib = (n) => {
    if(n <= 1) return n;
    
    return Fib(n-1) + Fib(n-2);
}
console.log(Fib(7));

coderbyte.com

From this tree diagram, we can see that to calculate Fib(7), we have to calculate Fib(6) and Fib(5). And to calculate Fib(6), Fib(5) needs to be calculated again along with Fib(4) and this cycle goes on.

Estimated Time Complexity: O(2^n)

Estimated Space Complexity: O(n)

Memoization is a technique in which we store the solutions of sub-problems so that we can use them later where required, hence the repetition is avoided.

Let’s look at memoized solution:

const Fib = (n, memo={}) => {
    if(n in memo) return memo[n];
    if(n <= 1) return n;
    
    memo[n] = Fib(n-1, memo) + Fib(n-2, memo);
    return memo[n];
}
console.log(Fib(7));

The Fib(2), Fib(3), Fib(4), Fib(5) are calculated once and stored in memo object for later use. Hence this approach calculates result much faster.

Estimated Time Complexity: O(n)

Estimated Space Complexity: O(n)

Tabulation:

Using this technique, a dynamic problem is solved iteratively instead of recursion. Basically, after determining the relation between main problem and its sub-problems, we start from the very base case and solve up till the main problem. The results are stored in a data structure suitable to kind of problem.

Let’s solve same Fib(n) problem using this method:

const Fib = (n) => {
    const sequence = new Array(n+1).fill(0);
    
    //base case
    sequence[0] = 0;
    sequence[1] = 1;
    // relation: sequence[i] = sequence[i-1] + sequence[i-2];
    
    for(let i = 2; i <= n; i++){
        sequence[i] = sequence[i-1] + sequence[i-2];
    }
    return sequence[n];
}
console.log(Fib(n));

This is another way of optimizing a dynamic problem solution.

Estimated Time Complexity: O(n)

Estimated Space Complexity: O(n)

Both Memoization and Tabulation are effective to reduce execution time and memory of a dynamic programming algorithm. In, Memoization, we tackle this by storing results for later use and in Tabulation, iterative approach is taken instead of recursion.