Memoization & Tabulation in Dynamic Programming

What is Dynamic Programming?

Dynamic Programming (DP) is an algorithmic technique to solve problems by breaking them down into overlapping subproblems and storing results to avoid redundant computations.

Memoization (Top-Down Approach)

Memoization is a technique where you store (cache) the results of expensive function calls and return the cached result when the same inputs occur again.

Implemented with recursion.
Solves problems "top-down", solving the original problem by recursive calls moving toward base cases.
Uses extra memory to store intermediate results, typically in a hash map or array.

Example: Fibonacci using Memoization

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

print(fib_memo(10))  # Output: 55

Tabulation (Bottom-Up Approach)

Tabulation solves the problem "bottom-up" by solving all related subproblems first, typically using iteration and filling up a table (often an array).

Implemented with iteration.
Builds the solution from base cases up toward the original problem.
Generally more space-efficient since it avoids recursion stack overhead.

Example: Fibonacci using Tabulation

def fib_tab(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

print(fib_tab(10))  # Output: 55

Key Differences Between Memoization and Tabulation

Aspect	Memoization	Tabulation
Approach	Top-down (recursive)	Bottom-up (iterative)
Implementation	Recursion with caching	Iterative loop filling DP table
Performance	Slower due to recursion overhead	Usually faster, no recursion overhead
Memory	Extra memory for recursion stack and memo table	Memory for DP table only
Execution order	Computes only needed states (on demand)	Computes all states systematically

When to Use?

Use memoization when the problem is easier to conceptualize recursively and some subproblems may not need calculation.
Use tabulation when iterative solutions are simpler or recursion depth is a concern.