Dynamic Programming

You already met dynamic programming's core idea in the Recursion course: memoization, caching subproblem results so nothing gets recomputed. DP formalizes that into two flavors:

• Top-down: plain recursion + a memo dict (what fib_memo did).
• Bottom-up: an iterative loop that fills a table from the smallest subproblem up to the answer — usually the more common style in practice, and avoids recursion-depth limits entirely.

A problem is a DP candidate when it has:

1. Overlapping subproblems — the same smaller subproblem gets solved multiple times in a naive approach (fib(5) needs fib(3) twice).
2. Optimal substructure — the optimal answer can be built from optimal answers to subproblems.

For problems with more than one input dimension, the table becomes an array indexed by the subproblem parameter. Coin change: dp[a] holds the fewest coins to make amount a, built up from dp[0] = 0:

def coin_change(coins, amount):
    dp = [0] + [float("inf")] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != float("inf") else -1

Every dp[a] only depends on smaller dp[a - c] values that were already computed earlier in the loop — that ordering is what makes bottom-up work without recursion.