Dynamic programming without the fear

When DP applies

Two conditions. Overlapping subproblems: the same smaller question is asked many times, so caching pays. Optimal substructure: the best answer to the whole is built from best answers to the parts.

Naive Fibonacci has both — fib(30) recomputes fib(10) thousands of times. Caching turns exponential into linear. If subproblems do not repeat, caching buys nothing and you want divide and conquer instead.

Then write the transition

With the state named, ask: what was the last decision that led here, and what state was I in before it? For coin change the last decision was picking some coin c, and before it I was at amount i − c. So dp[i] = min over coins of dp[i − c] + 1.

Finally set the base case — dp[0] = 0, since zero coins make amount zero — and decide the iteration order so every value is computed before it is read.

def coin_change(coins, amount):
    INF = float('inf')
    dp = [0] + [INF] * amount        # dp[a] = fewest coins making exactly a
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return -1 if dp[amount] == INF else dp[amount]

Note: Initialising to 0 instead of infinity would make unreachable amounts look reachable.

Top-down or bottom-up?

Top-down is recursion plus a cache — often just `@lru_cache` on the recursive function. It is easier to write because it follows the recurrence directly, and it only computes states you actually need.

Bottom-up fills a table iteratively. It avoids recursion depth limits and permits the space optimisation below. It also forces you to think about iteration order, which is where the 0/1 versus unbounded knapsack distinction lives.

# UNBOUNDED knapsack — each item reusable
for item in items:
    for w in range(item.weight, capacity + 1):        # ascending
        dp[w] = max(dp[w], dp[w - item.weight] + item.value)

# 0/1 knapsack — each item used at most once
for item in items:
    for w in range(capacity, item.weight - 1, -1):    # DESCENDING
        dp[w] = max(dp[w], dp[w - item.weight] + item.value)

Note: Ascending lets the same item be picked again within one pass; descending reads only the previous item's values. The loop direction is the entire difference.

Rolling the table down

Most 2-D recurrences only read the previous row. If you need just the final value and not the reconstruction, keep one or two rows instead of the whole table — O(n · m) space becomes O(m).

That is the standard fix when a correct DP exceeds the memory limit. Note that memoised recursion usually uses more memory than bottom-up, not less, because of the call stack on top of the cache.

The families worth recognising