Coin Change

LeetCode 322 · View on LeetCode

Find the minimum number of coins needed to make a target amount. Each denomination can be used unlimited times. Unbounded knapsack with left-to-right iteration.

def coin_change(coins: list[int], amount: int) -> int:
    dp = [amount + 1] * (amount + 1)
    dp[0] = 0
    for coin in coins:
        for w in range(coin, amount + 1):
            dp[w] = min(dp[w], dp[w - coin] + 1)
    return dp[amount] if dp[amount] <= amount else -1

if __name__ == '__main__':
    print(coin_change([1, 3, 4], 6))   # 2 (3+3)
    print(coin_change([1, 5, 10], 12)) # 3 (10+1+1)
    print(coin_change([2], 3))          # -1