Dynamic programming part – 1(Memoization)

Dynamic Programming is mainly an optimization over plain recursion. Wherever we see a recursive solution with repeated calls for the same inputs, we can optimize it using Dynamic Programming. The idea is to simply store the results of subproblems so that we do not have to re-compute them when needed later. In case you want to get clear about recursion first just go through this blog beforehand. This is part one of the dynamic programming blog series.

Types of dynamic programming

• Memoization: Top Down
• Tabulation: Bottom Up

We are going to talk about the Memoization approach in this part one of the Dynamic programming blog series.

Memoization

Memoization is similar to a recursive process, just in this case we store the result of already solved subproblems. So we don’t have to go through and calculate all the similar subproblems when they repeat. That saves a significant amount of time as we don’t have to solve the repeated subproblems once it occurs for the second time. we just return the already stored result. Enough of theory let’s just solve a recursive problem with memoization.

As Memoization refers to the technique of caching and reusing previously computed results. we will be doing it by discussing the famous Fibonacci problem.

If you’re computing for instance fib(3) (the third Fibonacci number), a naive implementation would compute fib(1) twice:

With a DP implementation, the tree could look like this.

It doesn’t look impressive in that small example though. but it’s in fact enough to bring down the complexity from O(2ⁿ) to O(n). Here’s a better illustration that compares the full call tree of fib(7) (left) to the optimized graph.

A memoized fib function would thus look like this:

fib(n) {
    // only calculate if not memoized. else return mem[n]
    if (!mem[n])
        if (n < 2) result = n
        else result = fib(n-2) + fib(n-1)
        //Here we are storing the result of current fib(n)
        mem[n] = result

    return mem[n]
}

As you can see fib(k) will only be computed at most once for each k [k refers to the current n, for n = 4, k = 4,3,2,1]. (Second time around it will return the memoized value.)

To get more details about dynamic programming I would suggest watching this video.

List of dynamic problems to practice. If you want to know more about or just to connect with me follow me on Twitter or text me here. Till then happy coding.