How It Works

Most DP solutions are designed with the same five questions. This chapter applies them to two classic problems, minimum coin change and longest common subsequence (LCS), and traces the tables by hand so you can see the answers being built.

A five-step recipe

1. State: what parameters identify a subproblem? Pick the smallest set that still determines the answer.
2. Recurrence: how is a state's answer computed from smaller states? This usually means "try every choice and keep the best".
3. Base cases: which states are trivial?
4. Order: in which order must states be computed so that dependencies are ready? (Memoization finds the order automatically.)
5. Answer: which state holds the final result, and do you also need to reconstruct the choices?

Example 1: minimum coin change

Given coin denominations [1, 3, 4] (unlimited supply of each) and an amount of 6, what is the fewest number of coins that adds up to exactly 6?

A greedy approach takes the largest coin first: 4, then 1, then 1, which is three coins. But 3 + 3 uses only two. Greedy fails, so we use DP.

• State: dp[a] = fewest coins that sum to amount a.
• Recurrence: dp[a] = 1 + min(dp[a - c]) over every coin c with c <= a.
• Base case: dp[0] = 0. Unreachable amounts stay at infinity.
• Order: increasing a, because dp[a] depends only on smaller amounts.
• Answer: dp[6].

Filling the table from left to right:

The answer is dp[6] = 2. Following the "Last coin" column backwards gives the coins themselves: from 6 take a 3 and move to 3, take a 3 and move to 0.

import math


def min_coins(coins: list[int], amount: int) -> tuple[int, list[int]]:
    dp = [0] + [math.inf] * amount
    last = [0] * (amount + 1)
    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
                last[a] = c
    if dp[amount] == math.inf:
        return -1, []
    used, a = [], amount
    while a > 0:
        used.append(last[a])
        a -= last[a]
    return dp[amount], used


print(min_coins([1, 3, 4], 6))  # (2, [3, 3])
print(min_coins([5, 10], 3))    # (-1, [])

The same recurrence written top-down reads almost like the definition. The cache makes sure each amount is solved only once.

import math
from functools import cache


def min_coins(coins: tuple[int, ...], amount: int) -> int:
    @cache
    def best(a: int) -> float:
        if a == 0:
            return 0
        return min((1 + best(a - c) for c in coins if c <= a), default=math.inf)

    result = best(amount)
    return -1 if result == math.inf else int(result)


print(min_coins((1, 3, 4), 6))  # 2

Example 2: longest common subsequence

A subsequence keeps characters in order but may skip some. For a = "ABCBA" and b = "BCAB", what is the longest string that is a subsequence of both?

• State: L[i][j] = LCS length of the first i characters of a and the first j characters of b.
• Recurrence: if a[i-1] == b[j-1], then L[i][j] = L[i-1][j-1] + 1; otherwise L[i][j] = max(L[i-1][j], L[i][j-1]).
• Base cases: L[0][j] = L[i][0] = 0 (an empty prefix shares nothing).
• Order: row by row, left to right. Each cell needs the cell above, to the left, and diagonally up-left.
• Answer: L[5][4].

The bottom-right cell says the LCS has length 3. To recover one, start there and walk back: on a match, take the character and move diagonally; otherwise move toward the larger neighbor. Ties can lead to different but equally long answers, such as "BCB" and "BCA".

def lcs_table(a: str, b: str) -> list[list[int]]:
    L = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                L[i][j] = L[i - 1][j - 1] + 1
            else:
                L[i][j] = max(L[i - 1][j], L[i][j - 1])
    return L


for row in lcs_table("ABCBA", "BCAB"):
    print(row)
# last row printed: [0, 1, 2, 3, 3]

Summary

• Design a DP by answering five questions: state, recurrence, base cases, order, answer.
• Tracing a small table by hand is the fastest way to check a recurrence.
• Store the choice made at each state (or walk the table backwards) to reconstruct the actual solution, not just its value.