Dynamic Programming for Beginners: Memoization vs Tabulation

Dynamic Programming (DP) is a powerful technique for solving optimization problems by breaking them into smaller subproblems.

The Core Idea

DP solves problems by:

1. Breaking them into overlapping subproblems

2. Storing results to avoid recomputation

3. Building up solutions from smaller solutions

Memoization (Top-Down)

Memoization uses recursion with caching:

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

Pros:

- Intuitive (follows problem structure)

- Only computes needed subproblems

Cons:

- Recursion overhead

- Stack overflow risk for deep recursion

Tabulation (Bottom-Up)

Tabulation builds solutions iteratively:

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

Pros:

- No recursion overhead

- Better space optimization possible

Cons:

- May compute unnecessary subproblems

- Less intuitive for some problems

When to Use Which?

- **Memoization:** When you don't need all subproblems

- **Tabulation:** When you need all subproblems or want to optimize space

Classic DP Problems

1. **Fibonacci:** Basic DP introduction

2. **Climbing Stairs:** Similar to Fibonacci

3. **Coin Change:** Optimization problem

4. **Longest Common Subsequence:** 2D DP

Start with these to build your DP intuition!