Dynamic Programming: The Basics - When & Why ? - Part 1

Let's understand Dynamic Programming, when and why to use it, and explored a few basic examples.

Welcome back, brave coder 👨‍💻, to the world of Dynamic Programming (DP)! DP may sound like some sort of advanced/hard concept (that’s what I though too, the first time I heard it haha), but don't worry, it's just a programming trick to use, not a high-level complex algorithm or anything of that sense!

In this guide, we’ll look at the fundamentals of Dynamic Programming and implement it with a few basic examples using JavaScript (that’s my favorite language so far for problem-solving after python, due to its syntax simplicity…).

Okay, let’s not waste more time! Let’s Gooo!

---

🌌 What is Dynamic Programming?

Dynamic Programming (DP) is a strategy for solving problems by breaking them down into smaller parts and storing solutions of those parts, so you can reuse them later. (very simple right?)

Imagine trying to remember every friend’s phone number individually 😱 versus keeping a contact list ✅ → DP is the contact list!

PS: ‘DP’ is an abreviation of ‘Dynamic Programming’ (I’m so lazy to type it everytime 😂). Okay let’s go back to DP explanation…

In Other Words:

• DP helps us avoid redundant work by storing answers to problems we’ve already solved.

• It’s great for problems with lots of repetitive calculations or overlapping tasks.

---

❓ When to Use Dynamic Programming?

You can use DP if:

• The problem can be broken down into smaller sub-problems.

• Solving one part of the problem helps solve other parts of the problem.

• You keep repeating the same calculations again and again (useless waste of memory).

Two common types of problems where DP shines are:

1. Fibonacci sequences (we’ll see it in the next chapters).

2. Pathfinding (like when trying to find the shortest route in a maze).

---

👨‍🍳The Key Ingredients of Dynamic Programming

Dynamic Programming has two main methods for keeping things efficient and speedy:

1. Memoization (Top-Down Approach)

• Think of memoization as a memory trick where you “remember” answers to sub-problems as you solve them.

• This way, you never have to calculate the same thing twice.

• In code, you use an object or array to store results of previous calculations.

2. Tabulation (Bottom-Up Approach)

• In tabulation, you start from the smallest sub-problems and build up to the final solution.

• This usually involves filling up a table (or array) step-by-step until you reach the big answer.

• Tabulation is often a bit faster than memoization but can be trickier to set up (but don’t worry, you’re in the right place, nothing can trick us lol)

Now, let’s see some examples in JavaScript, where we’ll make use of our DP skills!

---

🧩 DP in Code: Fibonacci Sequence

The Fibonacci sequence is a series of numbers, where each number is the sum of the two before it. It starts like this: 0, 1, 1, 2, 3, 5, 8, 13, …

In other words:

• fib(0) = 0

• fib(1) = 1

• fib(n) = fib(n - 1) + fib(n - 2)

Let's say we want to find fib(50). Without DP, calculating each term again and again would take forever (and make our computer cry).

❌ Naive (Brute Force) Solution:

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

With this method, fib(50) would take a very long time to calculate, because it recalculates the same numbers over and over again.

✅ Memoized (Top-Down) Solution:

Let’s add some memoization! We’ll use an object to store calculated values, so we don’t repeat work:

function fib(n, memo = {}) {
    if (n <= 1) return n;
    
    // Check if the result is already in the memo
    if (n in memo) return memo[n];  
    
    // Store result in memo
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);  
    
    return memo[n];
}

console.log(fib(50));  // Now it’s much faster!

With this approach, each Fibonacci number only gets calculated once. The results are stored in the memo object and used whenever needed (notice that we pass the memo object as an argument, so it can be accessible in every function call). Much faster, much cooler!

---

🔮 Conclusion

Dynamic Programming is a powerful tool for solving complex problems by breaking them down into manageable parts and reusing solutions. In this article, we’ve laid the foundation by understanding when and why to use DP and explored a few basic examples in JavaScript.

But don’t worry if memoization and tabulation still feel a bit mysterious, we’re just scratching the surface! In the next articles, we’ll dive deep into memoization and tabulation individually. We’ll explore how each technique works in detail, tackle more examples, and discuss when to use one approach over the other.

Stay tuned, and let’s keep leveling up our DP skills together!

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