Top-Down vs Bottom-Up

The Idea

Two directions, one recurrence. Top-down starts at the full problem, recurses, and caches whatever it meets — so it touches only the subproblems it actually needs. Bottom-up starts at the base cases and fills a table forward, so every dependency is ready before it is read. Top-down is easier to derive from the recursion; bottom-up avoids deep call stacks.

Real-World Example

Revising for an exam. Top-down means opening the hardest past paper and looking things up only when a question demands them. Bottom-up means working the syllabus chapter by chapter, so nothing is ever missing when you reach the paper — though you also study pages the paper never asks about.

The Code

def top_down(n, memo):
    if n < 2:
        return n
    if n not in memo:                                        # solve on demand
        memo[n] = top_down(n - 1, memo) + top_down(n - 2, memo)
    return memo[n]

def bottom_up(n):
    table = [0, 1] + [0] * (n - 1)                           # base cases first
    for i in range(2, n + 1):                                # dependency order
        table[i] = table[i - 1] + table[i - 2]
    return table[n]

print(top_down(30, {}), bottom_up(30))   # 832040 832040