DP Basics & Memoization 10 XP Easy

Ctrl+Enter Run Ctrl+S Save

Dynamic Programming (DP) is a technique for solving complex problems by breaking them into simpler overlapping subproblems. It's one of the most important topics in coding interviews! 🧩

💡 Think of it like this: Imagine someone asks you "What's 1+1+1+1+1+1+1+1?" You count and say "8". Then they ask "What's 1+1+1+1+1+1+1+1+1?" Instead of counting all over again, you say "9!" — because you remembered the answer to the previous question and just added 1. That's DP!

DP = Remembering past answers to avoid repeating work.

Let's see it with the Fibonacci sequence (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55...):

# ❌ Naive recursion: O(2^n) — TERRIBLE! Recalculates everything
def fib_bad(n):
    if n <= 1: return n
    return fib_bad(n-1) + fib_bad(n-2)  # Same work done over and over!

# ✅ DP with memoization: O(n) — FAST! Remember past answers
def fib_memo(n, memo={}):
    if n <= 1: return n
    if n in memo: return memo[n]         # Already solved? Use saved answer!
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

# ✅ Bottom-up tabulation: O(n) time, O(1) space — BEST!
def fib_tab(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

Two approaches to DP:

🔝 Top-down (Memoization): Start from the big problem, break it down, cache results. Uses recursion + a dictionary.
🔽 Bottom-up (Tabulation): Start from the smallest subproblems, build up to the answer. Uses loops + array/variables.
🔑 The key question: What are the subproblems? What's the recurrence relation?
📐 DP = Recursion + Memoization = Overlapping Subproblems + Optimal Substructure

Why is naive Fibonacci so slow? To calculate fib(5), it recalculates fib(3) twice, fib(2) three times! With memoization, each value is calculated only ONCE.

📋 Instructions

Compute the 10th Fibonacci number using bottom-up tabulation (O(1) space). Print the result.

Use two variables a, b starting at 0, 1. Loop n times: a, b = b, a + b. This is bottom-up DP — building the answer from the base cases up.

🧪 Test Cases

Input

fibonacci(10)

Expected

55

Test case 1

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›