Dynamic Programming: Tabulation - Part 3

Let's explore another amazing and powerful way to use Dynamic Programming, called "Tabulation"!

Welcome back, brave coder 👨‍💻, to part 3 of our dynamic programming series. In this adventure, we'll meet a little warrior called “Tobby the tabulator” who conquers challenges (subproblems) by solving each part systematically. Tobby uses Tabulation as his superpower to solve problems using a “bottom-up-approach”, no hashmaps, no recursion, just using simple tables (arrays) and simple logic (simple 😅)!

Let’s start the adventure and meet Tobby! Ala barakati Lah!

---

Chapter 1: Let’s Meet the Brave Warrior, Tobby the Tabulator

Let’s meet our hero, Tobby the Tabulator, is a young warrior with a desire for solving problems. Instead of tackling the big, scary problem in one shot, Tobby is smart and uses a step-by-step approach, solving tiny problems first and then combining them to tackle the larger ones.

Tobby’s weapon of choice? Tabulation, a tool that uses tables (arrays) to store results of subproblems so they don't have to solve the same thing twice.

Looks Simple and efficient, right?

---

Chapter 2: The Quest Begins - Tobby Solves the Fibonacci Sequence

For their first quest, Tobby decides to tackle a classic: the Fibonacci Sequence.

In the Fibonacci sequence, each number is the sum of the two preceding ones, usually starting with 0 and 1. Mathematically, it looks like this:

\(Fib(n)=Fib(n−1)+Fib(n−2)\)

But Tobby doesn't want to keep recalculating those values again and again, like some naive recursive warrior 😅. Instead, Tobby will use a table to store the answers as they go.

Let’s set up the code to help Tobby!

---

Chapter 3: Tobby’s Tool - Building the Table

Here's how Tobby builds the table:

1. Create a table (array) to hold solutions for each Fibonacci number up to n.

2. Start from the base cases: Fib(0) = 0 and Fib(1) = 1.

3. For each position i from 2 to n, calculate Fib(i) by adding the previous two entries in the table.

4. When Tobby reaches Fib(n), he already completed the whole quest and can return the answer!

Let’s put this in JavaScript:

function fibonacci(n) {
    // Step 1: Create a table (array) to store solutions to subproblems
    const fibTable = [0, 1]; // Base cases: Fib(0) = 0, Fib(1) = 1

    // Step 2: Fill the table by calculating each Fibonacci number up to n
    for (let i = 2; i <= n; i++) {
        fibTable[i] = fibTable[i - 1] + fibTable[i - 2];
    }

    // Step 3: Return the result for Fib(n)
    return fibTable[n];
}

// Test Tabby's function
console.log(fibonacci(6)); // Output: 8 (Fib(6) is 8)

Explanation of Tobby’s Steps:

• fibTable[0] = 0 and fibTable[1] = 1 are the base cases.

• The loop calculates each Fibonacci number from 2 up to n, and stores it in fibTable.

• Finally, fibTable[n] holds the solution to Fib(n)!

---

Chapter 4: Why Tobby Loves Tabulation ?

Tobby the Tabulator knows that tabulation is powerful for a few reasons:

1. Efficiency: Unlike recursion, which can call the same function many times, Tobby only calculates each value once.

2. Space-saving: Tobby keeps just the needed solutions and discards everything else. Once Tobby’s done with a subproblem, it’s saved forever!

3. Easier Debugging: Tobby can always see the table and track every intermediate answer.

---

Chapter 5: Another Adventure with Tobby

Our brave Tobby now wants to conquer a new quest: the Climbing Stairs Problem.

In this problem, a player can take either 1 step or 2 steps at a time, and we want to know how many ways there are to reach the top if there are n stairs.

To solve this, Tobby realizes that the number of ways to reach step n, is just the sum of the ways to reach n-1 (if we take a 1-step) and n-2 (if we take a 2-step).

Code Time

Tobby’s strategy is nearly identical to the Fibonacci problem:

function climbStairs(n) {
    // If there are 0 or 1 stairs, there's only 1 way to climb
    if (n <= 1) return 1;

    // Step 1: Create a table to hold the number of ways to reach each step
    const ways = [1, 1]; // Base cases: 1 way to climb 0 or 1 stairs

    // Step 2: Fill the table for each step from 2 to n
    for (let i = 2; i <= n; i++) {
        ways[i] = ways[i - 1] + ways[i - 2];
    }

    // Step 3: Return the result for step n
    return ways[n];
}

// Test Tabby's function
console.log(climbStairs(5)); // Output: 8 (there are 8 ways to climb 5 stairs)

Explanation:

• Base cases: ways[0] = 1 and ways[1] = 1 (only one way to stay at 0 or take one step to the first stair).

• For each step i, calculate ways[i] by adding ways[i-1] (if they took 1 step) and ways[i-2] (if they took 2 steps).

• The answer is ways[n], which tells Tobby how many ways there are to climb n stairs.

---

Chapter 6: Tobby’s Tips for Future Quests

1. Use Tabulation for Bottom-Up Approach: When you can build solutions from the base cases up, tabulation is often easier and faster.

2. Pick the Right Table Size: Only store what’s needed. For example, sometimes, instead of a full table, you can save just the last two values!

3. Enjoy the Speed: Tabulation avoids unnecessary recursion, so no more repeated work and wasted time!

---

Last Chapter: Tobby’s Legacy

Now, Tobby the Tabulator is a legend in the kingdom of Dynamic Programming. With a simple table and a methodical approach, Tobby solved some of the toughest challenges and saved CPU cycles across the kingdom!

I hope that Tobby helped you, today, master a high level dynamic programming approach (Tabulation). If you have any further questions about Tobby’s approach (Tabulation), comment down below, and will be glad to ask Tobby to give you an answer haha!

That’s it for today’s article, see you in the next one, Ciao!

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