Dynamic Programming

Reuse answers instead of repeating work

Dynamic programming (DP) applies when a problem has overlapping subproblems and an optimal answer can be built from optimal answers to smaller states. Instead of solving the same state again, store its answer.

Consider counting ways to climb n stairs by taking one or two steps. Every route to stair n comes from stair n - 1 or n - 2, so:

ways(n) = ways(n - 1) + ways(n - 2)

with ways(0) = 1 and ways(1) = 1. Plain recursion branches twice and recomputes the same values. DP evaluates each stair once.

A five-part recipe

1. State: define exactly what one answer means, such as dp[i] = ways to reach stair i.
2. Transition: express a state using smaller states, here dp[i] = dp[i - 1] + dp[i - 2].
3. Base cases: supply the smallest answers directly.
4. Order: compute dependencies before the state that uses them.
5. Result: identify which state answers the original question.

Top-down and bottom-up

Memoisation starts with the original recursive question and caches each state on first use. It often mirrors the recurrence closely and may skip unreachable states, but it uses the call stack.

Tabulation starts at the base cases and fills a table in dependency order. It avoids recursion and can reveal when old states are no longer needed. For climbing stairs, only the previous two values matter, so O(n) table space can shrink to O(1).

Minimum coins as a complete example

For a target amount, let dp[x] be the fewest coins needed to make exactly x. To compute dp[x], try every coin c and extend dp[x - c]. An unreachable state stays at infinity.

This version also records the last coin used, allowing it to reconstruct one optimal solution rather than returning only the count.

def min_coins(coins, amount):
    inf = amount + 1
    dp = [0] + [inf] * amount
    used = [-1] * (amount + 1)
    for value in range(1, amount + 1):
        for coin in coins:
            if coin <= value and dp[value - coin] + 1 < dp[value]:
                dp[value] = dp[value - coin] + 1
                used[value] = coin
    if dp[amount] == inf:
        return None
    chosen, value = [], amount
    while value > 0:
        chosen.append(used[value])
        value -= used[value]
    return dp[amount], chosen


answer = min_coins([1, 3, 4], 6)
print("minimum:", answer[0])
print("coins:", " ".join(str(x) for x in answer[1]))
print("amount 2 with [3, 4]:", "impossible" if min_coins([3, 4], 2) is None else "possible")

minimum: 2
coins: 3 3
amount 2 with [3, 4]: impossible

Recognising DP problems

Look for questions that ask for a minimum, maximum, count or feasibility over many related choices. Then test whether two different decision paths can reach the same remaining state. If they can, caching that state may remove repeated work. Common state shapes include one index, two indices for subsequences, a grid cell, an index plus remaining capacity, and a compact mask of chosen items.