ZERO / HERO
Unlimited coins of each kind

Coin Change & Unbounded Knapsack

The analogy

Make 11p from coins of 1p, 2p and 5p, using as few coins as possible and as many of each as you like. Grabbing the biggest coin first seems obvious and is sometimes wrong, so instead you build up the answer for every amount from 0 to 11.

Visualizer

Building every amount

step 1 / 8
0123456
min coins0∞∞∞∞∞∞
using

Coins [1,3,4], make 6 with as few as possible. Unlimited copies of each — this is UNBOUNDED knapsack.dp[a] = fewest coins to make amount a

def min_coins(coins, amount):
    INF = float("inf")
    dp = [0] + [INF] * amount
    for c in coins:
        for a in range(c, amount + 1):     # ASCENDING = reuse
            dp[a] = min(dp[a], dp[a - c] + 1)
    return -1 if dp[amount] == INF else dp[amount]

def count_combinations(coins, amount):     # unordered
    dp = [1] + [0] * amount
    for c in coins:                        # coins OUTER
        for a in range(c, amount + 1):
            dp[a] += dp[a - c]
    return dp[amount]

def count_permutations(coins, amount):     # ordered
    dp = [1] + [0] * amount
    for a in range(1, amount + 1):         # amount OUTER
        for c in coins:
            if a >= c:
                dp[a] += dp[a - c]
    return dp[amount]
Check yourself

Counting ways to make an amount: coins in the OUTER loop counts…