TechPrep
Search spaces and optimisationReadLabPracticeCheck

Dynamic programming

Define the state, write the recurrence, fix the base case and fill the table in an order where every dependency is ready.

Coin Change. Given coin denominations coins (unlimited supply) and an amount, return the fewest coins that make the amount, or -1 if it cannot be made.

Signals that point here

The idea

Say four things before coding. State: dp[a] is the fewest coins for amount a. Recurrence: dp[a] = 1 + min(dp[a - c]) over coins c <= a. Base: dp[0] = 0. Order: increasing a, because dp[a] reads only smaller amounts.

Start top-down (recursion plus memo) if that is how you think, then convert to bottom-up if asked about stack depth or constant factors. Both are the same algorithm. Greedy (largest coin first) is wrong for coins like [1, 3, 4] and amount 6; giving that counter-example is a strong signal.

def coin_change(coins: list[int], amount: int) -> int:
    impossible = amount + 1                  # more coins than could ever be needed
    dp = [0] + [impossible] * amount         # dp[a] = fewest coins for a
    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] <= amount else -1

Complexity

O(amount · len(coins)) time, O(amount) space.

Pitfalls interviewers watch for

Variants worth knowing

Test it like the interviewer will

Step through it: coin_change([1, 3, 4], 6)

Each step is recorded from an instrumented copy of the Python above, run when the site was built.

Practice

Written for this site to drill the lesson. Not reported interview questions.

  1. Count the number of ways to climb n stairs taking 1 or 2 steps.
  2. Return the edit distance between two strings.
  3. Return the length of the longest increasing subsequence in O(n log n).

Check yourself

What four things should you state before coding a DP?

State, recurrence, base case, evaluation order.

Give a coin set where greedy fails.

[1, 3, 4] with amount 6: greedy gives 4+1+1 (3 coins), DP gives 3+3 (2 coins).

Saved in this browser.