RugvAI Labs

Recursion & Dynamic Programming: Solving Hard Problems

Recursion is how compilers parse source code, how LLMs tokenize text, and how DOM trees render in your browser. Dynamic programming is the technique that turns a 2^n exponential nightmare into an n² polynomial solution — and it's the #1 most-asked topic in LeetCode "Hard" interviews at Google and Meta. Master memoization once, and you'll see DP patterns everywhere.

Learning Objectives

After this lesson, you will be able to:

Understand how the call stack executes recursive function calls
Identify base cases and recursive cases in any recursive problem
Apply memoization (top-down DP) to eliminate redundant computation
Build bottom-up tabulation tables using the 5-question DP framework
Solve classic DP problems: coin change, knapsack, LCS, and edit distance
Choose between memoization and tabulation based on problem constraints
Apply two-pointer and sliding window patterns to array problems

Why

Why This Matters

Dynamic programming is the interview skill that separates senior engineers -- every major tech company asks DP questions because they test whether you can break ambiguous problems into overlapping subproblems, a skill directly transferable to designing ML training loops, scheduling, and optimization
Sequence alignment and edit distance power NLP -- the edit distance (Levenshtein) algorithm used in spell checkers, diff tools, and DNA sequence alignment is a 2D DP table. Understanding DP means you can reason about why BERT fine-tuning and CTC loss work the way they do
Memoization is the backbone of caching in distributed systems -- once you internalize the pattern of "compute once, store the result, reuse it," you will naturally apply it to API response caching, model prediction caching, and incremental computation pipelines

Prerequisites

Before You Start

Review

#Recursion: Functions Calling Themselves

A recursive function solves a problem by solving smaller versions of the same problem. Every recursive function needs exactly two things:

Base case — the simplest input where you can return immediately without recursing
Recursive case — how you reduce a larger input to a smaller one and combine results

Recursion Tree Visualizer — Watch the Call Stack GrowInteractive

Step through a recursive function call-by-call. Each recursive invocation spawns a new branch. Watch the tree grow on the way down and collapse on the way back up — exactly what Python's call stack does.

Loading visualization...

pythonrunnable cell

import sys

# Python's default recursion limit
print(sys.getrecursionlimit())  # 1000

# Increase if needed (use sparingly -- prefer iterative for deep recursion)
sys.setrecursionlimit(10000)

# Call stack visualization for factorial(4):
#
# factorial(4)                     <-- frame 4: waiting for factorial(3)
#   factorial(3)                   <-- frame 3: waiting for factorial(2)
#     factorial(2)                 <-- frame 2: waiting for factorial(1)
#       factorial(1)               <-- frame 1: BASE CASE returns 1
#     factorial(2) = 2 * 1 = 2    <-- frame 2 resumes, returns 2
#   factorial(3) = 3 * 2 = 6      <-- frame 3 resumes, returns 6
# factorial(4) = 4 * 6 = 24       <-- frame 4 resumes, returns 24

def factorial(n: int) -> int:
    """Compute n! recursively.

    Time: O(n) — n recursive calls
    Space: O(n) — n frames on the call stack simultaneously
    """
    if n <= 1:      # BASE CASE: stop recursing
        return 1
    return n * factorial(n - 1)  # RECURSIVE CASE: reduce to smaller problem

print(factorial(4))   # 24
print(factorial(10))  # 3628800

Hit RecursionError: maximum recursion depth exceeded? Either your base case never fires (infinite recursion — check the condition) or the problem genuinely needs more than 1000 frames (use iteration or sys.setrecursionlimit). See the error decoder for the diagnosis flow.

#Classic Recursion Examples

pythonrunnable cell

# --- 1. Factorial: O(n) time, O(n) space ---
def factorial(n: int) -> int:
    return 1 if n <= 1 else n * factorial(n - 1)


# --- 2. Naive Fibonacci: O(2^n) time, O(n) space ---
# This is intentionally bad — we will fix it in Section 4.
def fib_naive(n: int) -> int:
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)


# --- 3. Fast Power via squaring: O(log n) time ---
# Key insight: x^8 = (x^4)^2, so we halve the exponent each step.
def power(base: float, exp: int) -> float:
    """Compute base^exp in O(log exp) using recursive squaring."""
    if exp == 0:
        return 1
    if exp % 2 == 0:
        half = power(base, exp // 2)
        return half * half        # x^8 = (x^4)^2 — square the result
    return base * power(base, exp - 1)

print(power(2, 10))  # 1024.0
print(power(3, 5))   # 243.0


# --- 4. Sum a list without built-ins: O(n) ---
def sum_list(lst: list[int]) -> int:
    if not lst:         # base case: empty list
        return 0
    return lst[0] + sum_list(lst[1:])  # head + sum(tail)

print(sum_list([1, 2, 3, 4, 5]))  # 15


# --- 5. Flatten arbitrarily nested lists ---
def flatten(nested) -> list:
    """Recursively flatten a list of any nesting depth.

    flatten([1, [2, [3, 4]], 5]) → [1, 2, 3, 4, 5]
    """
    result = []
    for item in nested:
        if isinstance(item, list):
            result.extend(flatten(item))  # recurse into sublist
        else:
            result.append(item)
    return result

print(flatten([1, [2, [3, [4]], 5], 6]))  # [1, 2, 3, 4, 5, 6]


# --- 6. Recursive binary search: O(log n) ---
def binary_search(arr: list[int], target: int,
                  lo: int = 0, hi: int | None = None) -> int:
    """Return the index of target or -1 if not found."""
    if hi is None:
        hi = len(arr) - 1
    if lo > hi:
        return -1          # base case: search space exhausted
    mid = (lo + hi) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, hi)  # right half
    else:
        return binary_search(arr, target, lo, mid - 1)  # left half

print(binary_search([1, 3, 5, 7, 9, 11], 7))   # 3
print(binary_search([1, 3, 5, 7, 9, 11], 4))   # -1


# --- 7. Recursive merge sort: O(n log n) ---
def merge_sort(arr: list[int]) -> list[int]:
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return _merge(left, right)

def _merge(left: list[int], right: list[int]) -> list[int]:
    result, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    return result + left[i:] + right[j:]

print(merge_sort([5, 2, 8, 1, 9, 3]))  # [1, 2, 3, 5, 8, 9]


# --- 8. Generate all permutations: O(n * n!) ---
def permutations(lst: list) -> list[list]:
    """Generate all permutations of a list.

    Strategy: for each element, make it the first element,
    then recursively permute the rest.
    """
    if len(lst) <= 1:
        return [lst[:]]          # base case: one permutation of 0 or 1 elements
    result = []
    for i in range(len(lst)):
        lst[0], lst[i] = lst[i], lst[0]           # choose element i as first
        for perm in permutations(lst[1:]):
            result.append([lst[0]] + perm)         # prepend chosen element
        lst[0], lst[i] = lst[i], lst[0]           # restore (backtrack)
    return result

perms = permutations([1, 2, 3])
print(f"{len(perms)} permutations:", perms)
# 6 permutations: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

fib(4) — watch the call tree expand and collapse

Step 0 / 18

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Call stack

empty

1 / 19

#See the call stack itself, frame by frame

The tree above shows the shape of recursion. But what actually happens inside the interpreter is that each fib(...) or factorial(...) call pushes a stack frame with its own local variables, and returns pop those frames one at a time. Step through the LIFO discipline below — including a recursion preset (factorial(4)) and an exception-unwinding preset that pops frames without their return values.

Loading visualization...

#Now trace it yourself

The fib(4) tree above was pre-built. Now try YOUR own recursive function: edit the code, click Trace it, and watch the call stack grow on each factorial(n - 1) call, then unwind as each frame returns its product back up the chain.

pythonLive tracer· Trace a recursive callCtrl/⌘ + Enter to trace

Edit the code, then click Trace it. Python actually runs in your browser — every line, every variable, every print.

Click Trace it to capture the execution trace. The scrubber below will let you step through every variable change line-by-line.

Notice that fib(2) is computed twice — once under fib(3), once under fib(1)'s sibling. That redundancy explodes as n grows: fib(40) makes hundreds of millions of calls. The next section quantifies the damage, then Section 4 fixes it with memoization.

#The Problem with Naive Recursion

Let us trace the call tree for fib_naive(5):

                     fib(5)
                    /       \
                fib(4)      fib(3)
               /     \      /    \
           fib(3)  fib(2) fib(2) fib(1)
           /   \    /  \   /  \
        fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
        /   \
     fib(1) fib(0)

Count how many times fib(2) is called: 3 times. fib(3) is called 2 times. For fib(40), fib(2) is called hundreds of millions of times. We are recomputing the same values over and over.

pythonrunnable cell

import time

def fib_naive(n: int) -> int:
    """Naive recursive fibonacci. Time: O(2^n), Space: O(n) stack depth."""
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

# Count actual calls to see the explosion
call_count = 0
def fib_counted(n: int) -> int:
    global call_count
    call_count += 1
    if n <= 1:
        return n
    return fib_counted(n - 1) + fib_counted(n - 2)

for n in [10, 20, 30, 35]:
    call_count = 0
    result = fib_counted(n)
    print(f"fib({n:>2}) = {result:>10,}  |  calls: {call_count:>12,}")

# fib(10) =         55  |  calls:           177
# fib(20) =      6,765  |  calls:        21,891
# fib(30) =    832,040  |  calls:     2,692,537
# fib(35) =  9,227,465  |  calls:    29,860,703

# At n=50, this would take minutes. At n=100, the universe ends first.
# The call count follows: calls(n) = fib(n+1) * 2 - 1 ≈ O(1.618^n)

What Do You Think?

fib_naive(40) makes about how many function calls?

The answer is about 330 million. The recursion tree for fib(n) has height n and is nearly a full binary tree, making it O(φ^n) ≈ O(1.618^n). For n=40: 1.618^40 ≈ 165 million leaf nodes, and roughly double that total nodes ≈ 330 million calls. This is why fib_naive(40) takes several seconds and fib_naive(100) is computationally impossible without memoization.

#Memoization: Top-Down Dynamic Programming

Memoization stores the result of each function call. Before computing, check the cache. If the answer is already there, return it immediately.

Watch how memoization and tabulation actually work — see every cache hit, miss, and table fill in real time:

Dynamic Programming — Memoization vs Tabulation AnimatedInteractive

Loading visualization...

pythonrunnable cell

import functools
import sys

# --- Naive baseline (needed for benchmark comparison below) ---
def fib_naive(n: int) -> int:
    """Naive recursive fibonacci. Time: O(2^n) — included here for benchmarking."""
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

# --- Method 1: @functools.lru_cache — the cleanest approach ---
@functools.lru_cache(maxsize=None)  # None = unlimited cache size
def fib_memo(n: int) -> int:
    """Memoized fibonacci. Time: O(n), Space: O(n).

    lru_cache intercepts each call. If fib_memo(k) was computed before,
    it returns the cached value instantly. Each unique n is computed ONCE.
    """
    if n <= 1:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

# Reset counter
call_count = 0
# With memoization: fib(n) makes exactly 2n-1 unique calls (not 2^n)
print(fib_memo(50))   # 12586269025 (instant!)
print(fib_memo(100))  # 354224848179261915075 (still instant)

# Inspect the cache
print(fib_memo.cache_info())
# CacheInfo(hits=99, misses=101, maxsize=None, currsize=101)
# Only 101 unique calls made for fib(100)!


# --- Method 2: Manual memo dict ---
def fib_manual_memo(n: int, memo: dict | None = None) -> int:
    """Memoized fibonacci with explicit dictionary."""
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]     # cache hit: return stored result
    if n <= 1:
        return n
    memo[n] = fib_manual_memo(n - 1, memo) + fib_manual_memo(n - 2, memo)
    return memo[n]         # store before returning

print(fib_manual_memo(100))  # 354224848179261915075


# --- Method 3: functools.cache (Python 3.9+, shorthand for lru_cache(maxsize=None)) ---
@functools.cache
def fib_cache(n: int) -> int:
    if n <= 1:
        return n
    return fib_cache(n - 1) + fib_cache(n - 2)


# Performance comparison
import time

def benchmark(label, fn, n):
    start = time.perf_counter()
    result = fn(n)
    elapsed = time.perf_counter() - start
    print(f"{label}: fib({n}) = {result} in {elapsed:.6f}s")

benchmark("Naive (n=35)", fib_naive, 35)          # ~1-2 seconds
benchmark("Memo  (n=35)", fib_memo, 35)            # ~0.000001 seconds
benchmark("Memo  (n=100)", fib_memo, 100)          # ~0.000001 seconds

Loading visualization...

#Tabulation: Bottom-Up Dynamic Programming

Tabulation flips the recursion around: instead of starting from the answer and recursing down, we start from the base cases and build up to the answer iteratively. No recursion, no call stack overhead, no stack overflow risk.

pythonrunnable cell

# --- Fibonacci: bottom-up tabulation ---

def fib_table(n: int) -> int:
    """Fibonacci via tabulation. Time: O(n), Space: O(n)."""
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[0] = 0   # base case
    dp[1] = 1   # base case
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]  # recurrence relation
    return dp[n]

print(fib_table(10))   # 55
print(fib_table(50))   # 12586269025


# --- Space-optimized: O(1) space (rolling array) ---
# Key observation: dp[i] only depends on dp[i-1] and dp[i-2].
# We don't need the whole table — just the last two values.

def fib_optimized(n: int) -> int:
    """Fibonacci with O(1) space using rolling variables."""
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for _ in range(2, n + 1):
        curr = prev1 + prev2
        prev2, prev1 = prev1, curr
    return prev1

print(fib_optimized(100))  # 354224848179261915075
print(fib_optimized(1000)) # A very large number, computed in microseconds


# --- Show the table for small n ---
def fib_table_verbose(n: int) -> int:
    """Same as fib_table but prints the table."""
    dp = [0] * (n + 1)
    dp[1] = 1
    print(f"Index: {list(range(n+1))}")
    print(f"Init:  {dp}")
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    print(f"Final: {dp}")
    return dp[n]

fib_table_verbose(8)
# Index: [0, 1, 2, 3, 4, 5, 6, 7, 8]
# Init:  [0, 1, 0, 0, 0, 0, 0, 0, 0]
# Final: [0, 1, 1, 2, 3, 5, 8, 13, 21]

#The DP Framework

Before writing any DP solution, answer these five questions:

pythonrunnable cell

# THE 5-QUESTION DP FRAMEWORK
# ================================================
# 1. WHAT IS THE STATE?
#    What information do I need to uniquely describe a subproblem?
#    → dp[i] = ? (or dp[i][j] for 2D problems)
#
# 2. WHAT IS THE RECURRENCE?
#    How does dp[i] relate to smaller subproblems dp[i-1], dp[i-2], etc.?
#    → dp[i] = some function of dp[i-1], dp[i-2], ...
#
# 3. WHAT ARE THE BASE CASES?
#    What are the smallest subproblems I can answer directly?
#    → dp[0] = ?, dp[1] = ?
#
# 4. WHAT ORDER DO I FILL THE TABLE?
#    Left to right? Right to left? Row by row?
#    → dp[i] must be computed after all subproblems it depends on
#
# 5. WHAT IS THE FINAL ANSWER?
#    Is it dp[n]? max(dp)? dp[-1][-1]?
#    → depends on the problem

# ---- EXAMPLE: Climbing Stairs ----
# Problem: n steps. Each move: climb 1 or 2 steps. How many distinct ways?
#
# 1. STATE: dp[i] = number of distinct ways to reach step i
# 2. RECURRENCE: dp[i] = dp[i-1] + dp[i-2]
#    (arrive from step i-1 by taking 1 step, or from step i-2 by taking 2 steps)
# 3. BASE CASES: dp[0] = 1 (one way to stay at ground), dp[1] = 1 (one way to reach step 1)
# 4. ORDER: left to right, i from 2 to n
# 5. ANSWER: dp[n]

def climb_stairs(n: int) -> int:
    """Count distinct ways to climb n stairs (1 or 2 steps at a time)."""
    if n <= 2:
        return n
    dp = [0] * (n + 1)
    dp[0] = 1   # base case: 1 way to be at the start
    dp[1] = 1   # base case: 1 way to reach step 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

for stairs in range(1, 8):
    print(f"climb_stairs({stairs}) = {climb_stairs(stairs)}")
# 1, 2, 3, 5, 8, 13, 21 -- the Fibonacci sequence!

Quick check

What does memoization actually do for a recursive function like fib(n)?

#Classic DP Problems

#Problem 1: Coin Change: Minimum Coins

pythonrunnable cell

def coin_change(coins: list[int], amount: int) -> int:
    """Find the minimum number of coins needed to make 'amount'.

    1. STATE:  dp[i] = minimum coins needed to make amount i
    2. RECURRENCE: dp[i] = min(dp[i - coin] + 1) for each coin <= i
       (use one coin of this denomination, then solve for the remainder)
    3. BASE CASE: dp[0] = 0 (0 coins needed to make amount 0)
    4. ORDER: left to right, i from 1 to amount
    5. ANSWER: dp[amount] if < infinity, else -1 (not achievable)

    Time: O(amount * len(coins)), Space: O(amount)
    """
    INF = float("inf")
    dp = [INF] * (amount + 1)
    dp[0] = 0  # base case

    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] + 1 < dp[i]:
                dp[i] = dp[i - coin] + 1

    return dp[amount] if dp[amount] != INF else -1


print(coin_change([1, 5, 10, 25], 36))  # 3 (25 + 10 + 1)
print(coin_change([2], 3))              # -1 (impossible with only coin=2)
print(coin_change([1, 2, 5], 11))       # 3 (5 + 5 + 1)

#Problem 2: Longest Common Subsequence (LCS)

pythonrunnable cell

def lcs(s1: str, s2: str) -> int:
    """Find the length of the longest common subsequence.

    A subsequence is a sequence that can be derived from another sequence by
    deleting some (or no) characters without changing the order of the remaining.
    e.g., LCS("ABCBDAB", "BDCAB") = 4 ("BCAB" or "BDAB")

    1. STATE: dp[i][j] = LCS length of s1[:i] and s2[:j]
    2. RECURRENCE:
       if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1  (characters match)
       else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])          (skip one character)
    3. BASE CASES: dp[0][j] = 0, dp[i][0] = 0 (empty string has LCS = 0)
    4. ORDER: row by row, left to right
    5. ANSWER: dp[m][n]

    Time: O(m * n), Space: O(m * n)
    """
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]


def lcs_with_string(s1: str, s2: str) -> str:
    """Return the actual LCS string by backtracking through the DP table."""
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    # Backtrack
    result = []
    i, j = m, n
    while i > 0 and j > 0:
        if s1[i-1] == s2[j-1]:
            result.append(s1[i-1])
            i -= 1; j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    return "".join(reversed(result))


print(lcs("ABCBDAB", "BDCAB"))           # 4
print(lcs_with_string("ABCBDAB", "BDCAB"))  # BCAB or BDAB
print(lcs("intention", "execution"))     # 5

#Problem 3: 0/1 Knapsack

pythonrunnable cell

def knapsack_01(weights: list[int], values: list[int],
                capacity: int) -> int:
    """Classic 0/1 Knapsack: maximize value within weight capacity.
    Each item can be taken at most once (0 or 1 times).

    1. STATE: dp[i][w] = max value using first i items with capacity w
    2. RECURRENCE:
       if weights[i-1] <= w:
           dp[i][w] = max(dp[i-1][w],               # skip item i
                          dp[i-1][w - weights[i-1]] + values[i-1])  # take item i
       else:
           dp[i][w] = dp[i-1][w]                    # item too heavy, must skip
    3. BASE CASES: dp[0][w] = 0 for all w (no items = no value)
    4. ORDER: row by row (outer = items, inner = capacity)
    5. ANSWER: dp[n][capacity]

    Time: O(n * capacity), Space: O(n * capacity)
    """
    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):
            # Option 1: skip item i
            dp[i][w] = dp[i - 1][w]
            # Option 2: take item i (if it fits)
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i][w],
                               dp[i - 1][w - weights[i - 1]] + values[i - 1])

    return dp[n][capacity]


# 4 items, capacity = 5
weights = [2, 3, 4, 5]
values  = [3, 4, 5, 6]
print(knapsack_01(weights, values, 5))   # 7 (items 0 and 1: weight 2+3=5, value 3+4=7)
print(knapsack_01(weights, values, 8))   # 10 (items 1 and 3: weight 3+5=8, value 4+6=10)

#Problem 4: Longest Increasing Subsequence (LIS)

pythonrunnable cell

def lis_dp(nums: list[int]) -> int:
    """Longest Increasing Subsequence. O(n^2) DP approach.

    1. STATE: dp[i] = length of LIS ending at index i
    2. RECURRENCE: dp[i] = max(dp[j] + 1) for all j < i where nums[j] < nums[i]
    3. BASE CASE: dp[i] = 1 for all i (each element is an LIS of length 1)
    4. ORDER: left to right
    5. ANSWER: max(dp)
    """
    if not nums:
        return 0
    n = len(nums)
    dp = [1] * n  # base case: every element alone is an LIS of length 1

    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:          # nums[j] can extend the sequence
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)


import bisect

def lis_binary_search(nums: list[int]) -> int:
    """LIS in O(n log n) using binary search (patience sorting).

    Maintain a 'tails' array: tails[k] = the smallest tail element
    of all increasing subsequences of length k+1.
    """
    tails: list[int] = []
    for num in nums:
        pos = bisect.bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)     # extend the longest subsequence
        else:
            tails[pos] = num      # replace to maintain smallest tails
    return len(tails)


seq = [10, 9, 2, 5, 3, 7, 101, 18]
print(f"LIS (O(n^2)):    {lis_dp(seq)}")            # 4 (2,3,7,18 or 2,5,7,18)
print(f"LIS (O(n log n): {lis_binary_search(seq)}")  # 4

#Problem 5: Edit Distance (Levenshtein)

pythonrunnable cell

def edit_distance(word1: str, word2: str) -> int:
    """Minimum edit operations (insert, delete, replace) to transform word1 → word2.

    Used in: spell checkers, diff tools, DNA alignment, NLP similarity metrics.

    1. STATE: dp[i][j] = min edits to transform word1[:i] into word2[:j]
    2. RECURRENCE:
       if word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1]  (no operation needed)
       else: dp[i][j] = 1 + min(
           dp[i-1][j],      # delete from word1
           dp[i][j-1],      # insert into word1
           dp[i-1][j-1]     # replace in word1
       )
    3. BASE CASES:
       dp[0][j] = j  (transform empty string to word2[:j] requires j insertions)
       dp[i][0] = i  (transform word1[:i] to empty string requires i deletions)
    4. ORDER: row by row
    5. ANSWER: dp[m][n]

    Time: O(m * n), Space: O(m * n)  [reducible to O(min(m,n)) with rolling row]
    """
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        dp[i][0] = i      # delete all of word1[:i]
    for j in range(n + 1):
        dp[0][j] = j      # insert all of word2[:j]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]   # characters match — free
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],      # delete word1[i-1]
                    dp[i][j - 1],      # insert word2[j-1]
                    dp[i - 1][j - 1],  # replace word1[i-1] with word2[j-1]
                )

    return dp[m][n]


print(edit_distance("kitten", "sitting"))   # 3
# kitten → sitten (replace k→s)
# sitten → sittin (replace e→i)
# sittin → sitting (insert g)

print(edit_distance("intention", "execution"))  # 5
print(edit_distance("", "abc"))                 # 3 (insert a, b, c)
print(edit_distance("abc", "abc"))              # 0 (already equal)

#Memoization vs Tabulation Comparison

	Memoization (Top-Down)	Tabulation (Bottom-Up)
Approach	Recursive + result cache	Iterative DP table
Time complexity	Same as tabulation	Same as memoization
Space complexity	Same + call stack frames	Table only (no stack)
Function call overhead	Yes — each subproblem is a function call	No — just array indexing
Stack overflow risk	Yes (Python limit ~1000 by default)	No recursion at all
Computes only needed states	Yes (lazy — only calls what is needed)	No (fills entire table)
Implementation style	Often closer to the mathematical definition	Requires understanding fill order
When to prefer	Quick prototyping, sparse state spaces	Production code, large n, space optimization

pythonrunnable cell

import functools

# Same problem, both styles side by side: Coin Change

# --- Top-Down (Memoization) ---
@functools.cache
def coin_change_memo(coins_tuple: tuple[int, ...], amount: int) -> int:
    if amount == 0:
        return 0
    if amount < 0:
        return float("inf")
    return 1 + min(coin_change_memo(coins_tuple, amount - c) for c in coins_tuple)

coins = (1, 5, 10, 25)
result = coin_change_memo(coins, 36)
print(f"Memo result: {result}")  # 3

# --- Bottom-Up (Tabulation) ---
def coin_change_tab(coins: list[int], amount: int) -> int:
    dp = [float("inf")] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for c in coins:
            if c <= i:
                dp[i] = min(dp[i], dp[i - c] + 1)
    return dp[amount] if dp[amount] != float("inf") else -1

print(f"Tab result:  {coin_change_tab([1, 5, 10, 25], 36)}")  # 3

Intuition

Build Your Intuition

Memoization is top-down with a sticky note. Tabulation is bottom-up with a spreadsheet.

Both eliminate redundant computation — they just work in opposite directions:

Memoization (top-down): Start at the big problem. Every time you need a subproblem's answer, check your sticky note (cache). If you have it, read it. If not, compute it recursively and write it down. You only compute what you actually need.

Tabulation (bottom-up): Start at the simplest base cases. Fill in the spreadsheet row by row until you reach the cell that holds the final answer. You always compute everything in a fixed order, even states that the final answer might not need.

pythonrunnable cell

import functools

# Same problem — Fibonacci — both ways:

# Memoization: write the recursive definition naturally, add cache
@functools.cache
def fib_memo(n):
    if n <= 1: return n
    return fib_memo(n-1) + fib_memo(n-2)
# Advantage: only computes needed states; reads like the math definition
# Disadvantage: function call overhead, stack overflow risk at large n

# Tabulation: fill an array from small to large
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]
# Advantage: no recursion, no stack overflow, easier to space-optimize
# Disadvantage: must figure out fill order; computes all states even if not needed

# When to choose which:
# - New to the problem? Write memoization first (easier to derive from math)
# - Need space optimization? Convert to tabulation (can collapse 2D → 1D)
# - n > 1000 in Python? Use tabulation (avoids recursion limit)

The 5-question framework works for both: define state, write recurrence, set base cases, determine fill order, locate the final answer.

Watch Out

Watch out

Fix: Identify ALL the information needed to uniquely describe each subproblem. For 0/1 Knapsack, the state must be dp[i][w] = max value using first i items with remaining capacity w. Collapsing to dp[i] loses the capacity dimension and makes the recurrence impossible to write correctly.

Using only the current index as the DP state when the subproblem also depends on a remaining budget, count, or capacity — e.g., defining dp[i] = 'max value at step i' for the knapsack problem.

The hallmark of DP is overlapping subproblems — two different paths through the recursion reach the same state. If your state definition is too narrow, you conflate distinct subproblems (same index but different remaining capacity) and the memoization gives wrong answers. When in doubt, ask: 'If I know only this state, can I compute the answer without knowing anything about how I got here?' If not, your state is incomplete.

Watch Out

Watch out

Fix: Convert mutable arguments to immutable equivalents before caching. Use tuple(arr) instead of list for sequences and tuple(sorted(d.items())) for dicts. Alternatively, use a manual memo dict keyed on a hashable representation.

Applying memoization to a recursive function that has mutable arguments (like lists or dicts), causing @functools.cache to raise TypeError because the arguments are not hashable

@functools.cache and @functools.lru_cache work by using the function arguments as dictionary keys. Dictionary keys must be hashable. Lists, dicts, and sets are not hashable — calling a cached function with a list argument raises TypeError immediately.

```python import functools

WRONG — list argument, cache raises TypeError

@functools.cache def count_subsets(nums: list, target: int) -> int: ...

TypeError: unhashable type: 'list'

RIGHT — convert to tuple (hashable)

@functools.cache def count_subsets(nums: tuple, target: int) -> int: if not nums or target < 0: return 0 return count_subsets(nums[1:], target) + count_subsets(nums[1:], target - nums[0])

Call site: convert the list to tuple

result = count_subsets(tuple([1, 2, 3]), 4) print(result) # 1

Alternative: manual memo dict with explicit key construction

def solve(nums, idx, target, memo=None): if memo is None: memo = {} key = (idx, target) # only cache the varying parts, not the whole list if key in memo: return memo[key] if idx == len(nums) or target < 0: return 0 result = solve(nums, idx+1, target, memo) + solve(nums, idx+1, target - nums[idx], memo) memo[key] = result return result ```

The manual memo dict approach is often cleaner because you choose exactly which parts of the state to key on, rather than requiring the entire argument to be hashable.

#Two Pointer and Sliding Window Techniques

These patterns often replace O(n^2) brute-force solutions with O(n) elegance.

#Two Pointers: Opposite Ends

pythonrunnable cell

# Pattern: left and right pointers move toward each other
def two_sum_sorted(nums: list[int], target: int) -> tuple[int, int] | None:
    """Find two indices that sum to target in a sorted array. O(n)."""
    left, right = 0, len(nums) - 1
    while left < right:
        current = nums[left] + nums[right]
        if current == target:
            return (left, right)
        elif current < target:
            left += 1   # need larger sum
        else:
            right -= 1  # need smaller sum
    return None

print(two_sum_sorted([1, 2, 3, 4, 6], 6))  # (1, 3) -- nums[1]+nums[3] = 2+4 = 6


def is_palindrome(s: str) -> bool:
    """Check if a string is a palindrome. O(n)."""
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1; right -= 1
    return True

print(is_palindrome("racecar"))  # True
print(is_palindrome("hello"))    # False

#Fast/Slow Pointers: Cycle Detection

pythonrunnable cell

# Pattern: slow moves 1 step, fast moves 2 steps
# If there is a cycle, they must eventually meet

def has_cycle(head) -> bool:
    """Detect a cycle in a linked list using Floyd's algorithm. O(n)."""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:   # they met — cycle detected
            return True
    return False


def find_duplicate(nums: list[int]) -> int:
    """Find the duplicate number in [1..n] array of length n+1. O(n), O(1) space.

    Treat array values as next-pointers: index 0 → nums[0] → nums[nums[0]] → ...
    The duplicate creates a cycle; cycle entry = duplicate number.
    """
    slow = fast = 0
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break
    # Find entry point of cycle
    slow = 0
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    return slow

print(find_duplicate([1, 3, 4, 2, 2]))  # 2
print(find_duplicate([3, 1, 3, 4, 2]))  # 3

#Sliding Window: Variable Size

pythonrunnable cell

def longest_substring_no_repeat(s: str) -> int:
    """Length of longest substring without repeating characters. O(n).

    Pattern: expand window right by advancing end;
             shrink window left when a repeat is found.
    """
    char_index: dict[str, int] = {}
    start = 0
    max_len = 0

    for end, char in enumerate(s):
        if char in char_index and char_index[char] >= start:
            start = char_index[char] + 1  # shrink: move start past the repeat
        char_index[char] = end
        max_len = max(max_len, end - start + 1)

    return max_len

print(longest_substring_no_repeat("abcabcbb"))  # 3 ("abc")
print(longest_substring_no_repeat("bbbbb"))     # 1 ("b")
print(longest_substring_no_repeat("pwwkew"))    # 3 ("wke")


def max_sum_subarray_k(nums: list[int], k: int) -> int:
    """Maximum sum of any subarray of size k. O(n).

    Fixed-size sliding window: add the new element on the right,
    remove the old element on the left.
    """
    window_sum = sum(nums[:k])
    max_sum = window_sum

    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]   # slide the window
        max_sum = max(max_sum, window_sum)

    return max_sum

print(max_sum_subarray_k([2, 1, 5, 1, 3, 2], k=3))  # 9 (subarray [5,1,3])

#Interactive Visualization: Recursion Tree & Memoization

Watch recursion trees expand in real time. Toggle memoization on/off to see how it prunes redundant branches and compare naive vs DP performance:

Recursion Tree & Memoization VisualizerInteractive

Loading visualization...

#Code Playground: DP Problems

pythonplayground.py · Pyodide

import functools

# ---- WARMUP: Fibonacci three ways ----
@functools.cache
def fib_memo(n):
  if n &lt;= 1: return n
  return fib_memo(n-1) + fib_memo(n-2)

def fib_tab(n):
  if n &lt;= 1: return n
  a, b = 0, 1
  for _ in range(2, n+1):
      a, b = b, a + b
  return b

print("fib(10) memo:", fib_memo(10))   # 55
print("fib(10) tab: ", fib_tab(10))    # 55

# ---- CHALLENGE 1: Climbing Stairs ----
# You can take 1, 2, or 3 steps at a time. How many ways to reach step n?
# Hint: dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
def climb_stairs_3(n: int) -> int:
  if n &lt;= 0: return 0
  if n == 1: return 1
  if n == 2: return 2
  if n == 3: return 4
  dp = [0] * (n + 1)
  dp[1], dp[2], dp[3] = 1, 2, 4
  for i in range(4, n + 1):
      dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
  return dp[n]

for i in range(1, 7):
  print(f"climb_stairs_3({i}) = {climb_stairs_3(i)}")

# ---- CHALLENGE 2: Coin Change ----
def coin_change(coins, amount):
  dp = [float("inf")] * (amount + 1)
  dp[0] = 0
  for i in range(1, amount + 1):
      for c in coins:
          if c &lt;= i:
              dp[i] = min(dp[i], dp[i - c] + 1)
  return dp[amount] if dp[amount] != float("inf") else -1

print("\nCoin change [1,5,10,25] -> 36:", coin_change([1,5,10,25], 36))  # 3
print("Coin change [2] -> 3:", coin_change([2], 3))                         # -1

# ---- CHALLENGE 3: Edit Distance ----
def edit_distance(w1, w2):
  m, n = len(w1), len(w2)
  dp = [[0]*(n+1) for _ in range(m+1)]
  for i in range(m+1): dp[i][0] = i
  for j in range(n+1): dp[0][j] = j
  for i in range(1, m+1):
      for j in range(1, n+1):
          if w1[i-1] == w2[j-1]:
              dp[i][j] = dp[i-1][j-1]
          else:
              dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
  return dp[m][n]

print("\nedit_distance('kitten','sitting'):", edit_distance("kitten","sitting"))  # 3
print("edit_distance('abc','abc'):", edit_distance("abc","abc"))                   # 0

# ---- CHALLENGE 4: Longest Common Subsequence ----
def lcs(s1, s2):
  m, n = len(s1), len(s2)
  dp = [[0]*(n+1) for _ in range(m+1)]
  for i in range(1, m+1):
      for j in range(1, n+1):
          if s1[i-1] == s2[j-1]:
              dp[i][j] = dp[i-1][j-1] + 1
          else:
              dp[i][j] = max(dp[i-1][j], dp[i][j-1])
  return dp[m][n]

print("\nlcs('ABCBDAB','BDCAB'):", lcs("ABCBDAB","BDCAB"))  # 4

Tests · Solve Fibonacci, Coin Change, Edit Distance, and LCS using dynamic programming!

#Key Takeaways

Every recursive function needs a base case and a recursive case -- the base case stops the recursion; the recursive case reduces the problem to something smaller. Missing the base case causes infinite recursion and stack overflow
Naive recursion with overlapping subproblems is O(2^n) -- fib(n) recomputes the same values exponentially. Adding @functools.cache transforms it to O(n) with one line
Memoization and tabulation have the same time complexity -- memoization is easier to write from the mathematical definition; tabulation is more efficient in practice (no function call overhead, no stack overflow risk, easier to space-optimize)
The 5-question DP framework unlocks any DP problem -- define the state, write the recurrence, set base cases, determine fill order, read the answer. Apply this before writing a single line of code
Space optimization reduces 2D tables to 1D -- when dp[i] only depends on dp[i-1], keep just two rows. For 0/1 Knapsack, reverse the inner loop to avoid counting the same item twice
Two-pointer and sliding window patterns are complementary to DP -- they solve different classes of problems (in-place array manipulation vs. optimal substructure) but both replace O(n^2) brute force with O(n)

Quick Check1 / 5

What is the time complexity of the naive recursive Fibonacci implementation fib(n) = fib(n-1) + fib(n-2)?

Your Reflection

Continue Learning

Discussion

Recursion & Dynamic Programming: Solving Hard Problems

After this lesson, you will be able to:

Before You Start

#Recursion: Functions Calling Themselves

#Classic Recursion Examples

fib(4) — watch the call tree expand and collapse

#See the call stack itself, frame by frame

#Now trace it yourself

#The Problem with Naive Recursion

#Memoization: Top-Down Dynamic Programming

#Tabulation: Bottom-Up Dynamic Programming

#The DP Framework

#Classic DP Problems

#Problem 1: Coin Change: Minimum Coins

#Problem 2: Longest Common Subsequence (LCS)

#Problem 3: 0/1 Knapsack

#Problem 4: Longest Increasing Subsequence (LIS)

#Problem 5: Edit Distance (Levenshtein)

#Memoization vs Tabulation Comparison

#Two Pointer and Sliding Window Techniques

#Two Pointers: Opposite Ends

#Fast/Slow Pointers: Cycle Detection

#Sliding Window: Variable Size

#Interactive Visualization: Recursion Tree & Memoization

#Code Playground: DP Problems

Space Optimization: Collapsing 2D DP Tables to 1D

#Key Takeaways