Dynamic Programming Foundations (Overlapping Subproblems)

Dynamic programming remembers answers to overlapping subproblems—recursion + memo or bottom-up table. You need optimal substructure or at least well-defined recurrence.

Why this shows up in the real world

Bioinformatics alignment (edit distance). Spell-check suggestions use weighted edit DP.

Core idea (explained for students)

Define state (indices, remaining capacity, mask subset), write transition, set base cases, fill in topological order of states.

Try this in Python

def fib(n: int, memo: dict[int, int] | None = None) -> int:
    if memo is None:
        memo = {}
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]


print(fib(30))

Common mistakes

• Exponential states from over-detailed masks.
• Forgetting modulo on counting problems.

Key takeaways

• Start from brute recursion with lru_cache to validate transitions.
• Draw the DAG of states for small examples.