Dynamic Programming in Python: Naive vs Memoized vs Tabulated Fibonacci, Plus 0/1 Knapsack

Fri Aug 14 2026

Dynamic programming solves a problem by breaking it into overlapping subproblems and reusing each subproblem’s answer instead of recomputing it. This post times fib(30) three ways — naive recursion, top-down memoization, and bottom-up tabulation — then solves a 0/1 knapsack problem with a DP table.

The code

import time


def fib_naive(n):
    # No memory of past results: recomputes the same subproblems over and
    # over, doubling roughly every step -> exponential time.
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)


def fib_memo(n, cache=None):
    # Top-down DP: cache each subproblem's result the first time it's
    # computed, reuse it on every later call instead of recomputing.
    if cache is None:
        cache = {}
    if n <= 1:
        return n
    if n in cache:
        return cache[n]
    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]


def fib_tab(n):
    # Bottom-up DP: build the table from the base cases up, no recursion.
    if n <= 1:
        return n
    table = [0] * (n + 1)
    table[1] = 1
    for i in range(2, n + 1):
        table[i] = table[i - 1] + table[i - 2]
    return table[n]


def knapsack(weights, values, capacity):
    # 0/1 knapsack: dp[i][w] = best value using the first i items with
    # capacity w. Either skip item i-1, or take it if it fits.
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            skip = dp[i - 1][w]
            if weights[i - 1] <= w:
                take = values[i - 1] + dp[i - 1][w - weights[i - 1]]
                dp[i][w] = max(skip, take)
            else:
                dp[i][w] = skip
    return dp[n][capacity]


n = 30
print(f"=== fib({n}): naive vs memo vs tabulation ===")

start = time.perf_counter()
naive_result = fib_naive(n)
naive_time = time.perf_counter() - start

start = time.perf_counter()
memo_result = fib_memo(n)
memo_time = time.perf_counter() - start

start = time.perf_counter()
tab_result = fib_tab(n)
tab_time = time.perf_counter() - start

print(f"fib_naive({n}) = {naive_result}, {naive_time:.6f}s")
print(f"fib_memo({n})  = {memo_result}, {memo_time:.6f}s")
print(f"fib_tab({n})   = {tab_result}, {tab_time:.6f}s")

print("\n=== 0/1 knapsack ===")
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 5
best = knapsack(weights, values, capacity)
print(f"weights={weights}, values={values}, capacity={capacity}")
print("best value:", best)

fib_naive recomputes overlapping subproblems with no cache; fib_memo adds a dict cache so each n is only computed once; fib_tab builds the same sequence bottom-up in a list, no recursion. knapsack fills a 2D DP table dp[i][w] where each cell is the best value achievable with the first i items and capacity w.

Running it

Real output:

=== fib(30): naive vs memo vs tabulation ===
fib_naive(30) = 832040, 0.074954s
fib_memo(30)  = 832040, 0.000030s
fib_tab(30)   = 832040, 0.000016s

=== 0/1 knapsack ===
weights=[2, 3, 4, 5], values=[3, 4, 5, 6], capacity=5
best value: 7

All three fib(30) implementations agreed on 832040, but the timings split sharply: fib_naive took 0.074954s, fib_memo took 0.000030s, and fib_tab took 0.000016s — memoization measured about 2498x faster than the naive version in this run, and tabulation about 4685x faster. For the knapsack with items (weight=2, value=3), (3, 4), (4, 5), (5, 6) and capacity=5, the DP table’s answer was 7 — the first two items together (weight 2+3=5, value 3+4=7) beat taking the single weight-5 item alone (value 6).

Takeaway

The run showed the same fib(30) answer computed three ways with wildly different timings once caching (memoization or tabulation) replaced recomputation, and the knapsack DP table found 7 as the best achievable value for the given weights, values, and capacity.