Implement Dynamic Programming SolversStep 2 of 5

Change-Making with Tabulation

12345

Step 2: Change-Making with Tabulation

Memoization solves subproblems top-down. Tabulation solves them bottom-up: you fill a table from the smallest subproblem upward, so the answer you need is always already computed.

Implement coin_change(coins, amount): return the minimum number of coins whose values sum to amount, or -1 if the amount cannot be formed. You may use each coin value any number of times.

Build a table dp where dp[a] is the fewest coins needed to make amount a. Start dp[0] equal to 0 (zero coins make zero) and mark every other entry as unreachable. For each amount a from 1 upward, try every coin c that is not larger than a: if dp[a - c] is reachable, then dp[a] can be dp[a - c] plus 1. Keep the smallest.

Examples:

  • coin_change([1, 2, 5], 11) returns 3 (5 + 5 + 1)
  • coin_change([2], 3) returns -1
  • coin_change([1, 2, 5], 0) returns 0
Hints
Starter code
def climb_stairs(n):
    """Number of ways to climb n stairs taking 1 or 2 steps, using memoization."""
    memo = {}

    def ways(k):
        if k < 0:
            return 0
        if k == 0:
            return 1
        if k in memo:
            return memo[k]
        memo[k] = ways(k - 1) + ways(k - 2)
        return memo[k]

    return ways(n)


def coin_change(coins, amount):
    """Minimum number of coins to make amount, or -1 if impossible (tabulation)."""
    # TODO: fill a dp table where dp[a] is the fewest coins to make amount a.
    # dp[0] = 0; every other entry starts unreachable (use amount + 1 as infinity).
    # For each a, try each coin c <= a: dp[a] = min(dp[a], dp[a - c] + 1).
    # Return dp[amount], or -1 if it stayed unreachable.
    pass
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

PreviousNext step