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:

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:

Cons:

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:

Cons:

When to Use Which?

Classic DP Problems

Start with these to build your DP intuition!