, ,
Share On

Claps upto fifty times for each post.

33


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(2n) 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.


One response to “Dynamic programming part – 1(Memoization)”

  1. hasanmisbah Avatar

    Very informative post. thanks, AKM for the great post.

Leave a Reply

Your email address will not be published. Required fields are marked *

AKM Elias Avatar

Click to follow this author!

4 Followers


Posts by this author

Share your local WordPress site.

24 February 2024

Dynamic programming! A blog generated by ChatGPT

08 December 2022

Dynamic programming part – 1(Memoization)

30 October 2022

Recursion & Recursive Solution

12 September 2022

Programming and The Ad Hoc problems.

28 August 2022


Posts related this

Share your local WordPress site.

AKM Elias

24 February 2024

Dynamic programming! A blog generated by ChatGPT

AKM Elias

08 December 2022

Dynamic programming part – 1(Memoization)

AKM Elias

30 October 2022

Let’s install Laravel valet on ubuntu

hasanmisbah

27 September 2022

GitHub SSH key setup takes Five minutes.

Hasanuzzaman

14 September 2022