Coin Change

Find the minimum number of coins needed to make up an amount.

Pattern fit

This is a great DP question because every amount depends on smaller amounts, and the recurrence forces you to consider all coin choices completely.

Key observation

For each amount a, the best answer is one more than the best answer of some reachable amount a - coin.

Target complexity

O(amount * coins) / O(amount)

How to break down the solution cleanly

This is a great DP question because every amount depends on smaller amounts, and the recurrence forces you to consider all coin choices completely.

For each amount a, the best answer is one more than the best answer of some reachable amount a - coin.

Name the state in plain language.

List the decisions that can transition into the state.

Reference implementation

Python

# Generic pattern template
# 1D DP
dp = [0] * (n + 1)
dp[0] = base
for i in range(1, n + 1):
    dp[i] = transition(dp, i)

# 2D DP
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, m + 1):
        dp[i][j] = transition(dp, i, j)