Dynamic Programming: Memoization - Part 2

Let's explore the concept of memoization and it's usefulness in the dynamic programming world!

Hello again brave coder 👨‍💻, before taking today’s adventure, make sure that you are ready, by checking the Dynamic Programming Part 1 article! If that’s already done, congrats! Now, let’s start today’s adventure!

Imagine you're playing a game 🎮 where you have to keep revisiting rooms 🚪, collecting diamonds💎. Every time you go into a room, you grab a diamond, and move to the next. But what if, at every time you collect a diamond from a room and go to the next room, you forget if you already collected the diamond from the previous room and you re-collect the diamond over and over !!!

Well, let’s introduce you to Memoization, your saver from doing the inefficient/boring work again and again and again, haha! Memoization is like placing a sticky note in each room door that says, "Hey, already collected the diamond💎here, skip this one!"

When you're programming with dynamic programming (DP), you want to solve problems efficiently. Memoization helps by saving already calculated answers, so your code doesn’t waste time resolving the same subproblems again.

Okay, that’s it for today’s article, see you in the next one 👋. Are you serious lol?? We just said “BissmiLah”, let’s have fun, enjoy!

---

🧠 Recap: What is Dynamic Programming (DP)?

Dynamic Programming is a strategy for solving complex problems by breaking them down into simpler subproblems. The two most popular techniques in DP are:

1. Memoization (Top-down approach): Storing answers as you calculate them.

2. Tabulation (Bottom-up approach): Building up answers from base cases.

We're focusing on Memoization, where we’re using memory to skip recalculating things. 🎩

---

📌 Let's Start with an Example: Fibonacci Sequence

The Fibonacci sequence is a classic example:

• Each number is the sum of the two preceding numbers.

• So: 0, 1, 1, 2, 3, 5, 8, 13...

But calculating Fibonacci numbers without memoization gets super slow as the numbers get bigger because you keep recalculating the same values!

---

❌ Step 1: Write a Basic (and Slow 🐢) Fibonacci Function

Let's start with a basic, no-memoization fibonacci function in JavaScript.

function fibonacci(n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

This works, but it’s like running back and forth to get coins from the same rooms repeatedly! Every time you call fibonacci(5), for example, you’ll recalculate fibonacci(4) and fibonacci(3), even though you already know their values.

fibonacci(5)
├── fibonacci(4)
│   ├── fibonacci(3) // repeated calculation
│   │   ├── fibonacci(2) // repeated calculation
│   │   │   ├── fibonacci(1) // repeated calculation
│   │   │   └── fibonacci(0) // repeated calculation
│   │   └── fibonacci(1) => 1
│   └── fibonacci(2)
│       ├── fibonacci(1) // repeated calculation
│       └── fibonacci(0) // repeated calculation
└── fibonacci(3)
    ├── fibonacci(2) // repeated calculation
    │   ├── fibonacci(1) // repeated calculation
    │   └── fibonacci(0) // repeated calculation
    └── fibonacci(1) => 1

TODO: Go now and calculate fibonacci of 100 😂😅

---

✅ Step 2: Let’s add Memoization 💾

Memoization is like saving the results of each subproblem the first time you solve it. Then, if you need it again, just grab it from your store, instead of recalculating it! In JavaScript, we can use an object or HashMap (in other languages) to store these results(key/value pairs).

Let’s memoize that Fibonacci function!

function fibonacci(n, memo = {}) {
    // Check if we already calculated this value
    if (n in memo) {
        return memo[n];
    }

    // Base case (preventing looping forever 😱😂)
    if (n <= 1) return n;

    // Calculate and store the result
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);

    return memo[n];
}

Now, whenever we calculate fibonacci(n), we store it in memo. If we need fibonacci(n) again, we can skip the recalculating part and fetch it from memo instead. Let’s break it down a bit more:

---

🚶‍♂️Step by Step of What’s Happening

Let’s pretend we call fibonacci(5):

1. Check memo for the Answer:

   • If n is already in memo, return the memoized value.

2. Calculate for New Values:

   • Since 5 isn’t in memo, we calculate it: fibonacci(4) + fibonacci(3).

3. Repeat the Process:

   • We go down the line, calculating fibonacci(4), fibonacci(3), and so on, memoizing as we go.

4. Collect the already calculated values:

   • When we need a value we’ve already calculated (e.g., fibonacci(3)), we grab it from memo instantly. No repeated work needed. 🎉

---

Step 4: Test It Out!

console.log(fibonacci(6)); // Try it with different numbers to see the magic!

TODO: Try the fibonacci memoization version, and the fibonacci old version with the value 50 for example, and compare the runtimes 😉!

---

💪 Why Memoization is Awesome!

Memoization is a game changer because it:

1. Saves Time: Avoids repeated calculations, making your code faster.

2. Reduces Complexity: Turns exponential-time problems into polynomial-time ones in many cases.

3. Boosts Efficiency: Perfect for recursive solutions, where subproblems repeat frequently.

Bonus: Use Map for Faster Lookups O(1)

Instead of an object, you could also use a Map to store your results for even faster access O(n) in some cases! Check this article to learn more about HashMaps!

function fibonacci(n, memo = new Map()) {
    if (memo.has(n)) return memo.get(n);
    if (n <= 1) return n;
    memo.set(n, fibonacci(n - 1, memo) + fibonacci(n - 2, memo));
    return memo.get(n);
}

---

🎉Wrapping Up Today’s Adventure!

And that’s it! Memoization is your secret weapon for killing recursive functions (positive way of killing, haha), making dynamic programming way easier to handle. So next time you're solving a problem, don’t forget to use memoization, to power up your algorithm🚀

In the next article, we’ll discover another powerful Dynamic Programming method with is Tabulation, stay tuned!

🔔 Don't forget to subscribe to my blog and YouTube channel to stay updated with all the latest content!