Skip to content
Deadline to Die

Module 2: Bottom-Up DP (The Building Blocks)

📚 Module 2: Bottom-Up Dynamic Programming

Course ID: DSA-402
Subject: The Building Blocks

Bottom-Up DP is the Professional’s Choice. It avoids recursion entirely and builds the answer using a simple loop.

🏗️ Step 1: The Table (Tabulation)

Instead of a “Mirror Room” of recursion, we use a simple Table (usually an Array or a 2D Grid).

  • We start at the Smallest problem (Base Case).
  • We use the small answers to build the next one.

🧩 The Analogy: Building a Lego Tower

  1. You place the 1st brick.
  2. You place the 2nd brick on top.
  3. You keep going until you reach the height you want.
  • Why? You don’t have to keep track of any “Recursive Calls.” You just look at the floor below you.

🏗️ Step 2: In Code (Iterative Fibonacci)

def fib(n):
    # 1. Create a table of size n+1
    table = [0] * (n + 1)
    
    # 2. Base cases
    table[0] = 0
    table[1] = 1
    
    # 3. Fill the table from left to right
    for i in range(2, n + 1):
        table[i] = table[i-1] + table[i-2]
        
    return table[n]

🏗️ Step 3: Why is Bottom-Up better?

  1. No Stack Overflow: Since there are no function calls, you can calculate the 1,000,000th Fibonacci number without crashing.
  2. Space Optimization: Often, you only need the last two values in the table. You can delete the rest to save memory! (O(1) Space).

🥅 Module 2 Review

  1. Bottom-Up: Starting from 11 and going up to NN.
  2. Tabulation: Filling in a table of results.
  3. Stability: Much safer for large inputs.

:::tip Final Senior Tip When you are in an interview, write the Top-Down solution first (it’s easier to talk through). Then, refactor to Bottom-Up to show you understand memory and performance! ::: Riverside. Riverside.