Memorization and Tabulation - Comparison

 hese are two core techniques in Dynamic Programming (DP), both used to optimize recursive or iterative algorithms by avoiding repeated work.

---

🧠 Memoization

Memoization is a top-down technique.

• You start with the original recursive function

• When a subproblem is solved, you store its result (usually in a dictionary or list)

• If the same subproblem is needed again, you reuse the stored result instead of recomputing it

✔ Improves recursive efficiency
✔ Only solves subproblems that are actually needed

Simple Example (Fibonacci)

def fib(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

Key idea: Cache results of recursive calls.

---

📊 Tabulation

Tabulation is a bottom-up technique.

• You build a table (often an array) iteratively

• Solve the smallest subproblems first

• Use those answers to build up to the final solution

✔ No recursion
✔ Usually faster in practice (no call stack overhead)

Example (Fibonacci)

def fib(n):
    table = [0, 1] + [0] * (n - 1)
    for i in range(2, n + 1):
        table[i] = table[i-1] + table[i-2]
    return table[n]

Key idea: Fill the DP table iteratively.

---

🔍 Summary Comparison

Feature	Memoization	Tabulation
Approach	Top-down	Bottom-up
Form	Recursion + cache	Iterative DP table
Solves…	Only required subproblems	All subproblems up to goal
Memory usage	Often smaller	Sometimes larger
Call stack overhead	Yes	No

---

Quick Memory Analogy 🎓

Technique	Analogy
Memoization	Remember answers as needed while working backward
Tabulation	Prepare a cheat sheet of all answers before working forward