Coin Change Problem in Python: Dynamic Programming That Actually Makes Sense

def coin_change(coins, amount):
    """
    Return the minimum number of coins to make `amount`.
    Returns -1 if the amount cannot be made with the given coins.
    """
    # dp[i] = minimum coins needed for amount i
    # Initialise with infinity (unreachable) for all amounts except 0
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0   # zero coins needed to make amount 0

    for coin in coins:
        for i in range(coin, amount + 1):
            # Using this coin: 1 + min coins for (i - coin)
            dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

# Example 1: solvable
print(coin_change([1, 2, 5], 11))
# Output: 3  (5 + 5 + 1)

# Example 2: also solvable with fewer coins
print(coin_change([1, 3, 4], 6))
# Output: 2  (3 + 3)

# Example 3: not solvable
print(coin_change([2], 3))
# Output: -1

def coin_change_verbose(coins, amount):
    """Same algorithm with table printed for learning purposes."""
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for coin in coins:
        for i in range(coin, amount + 1):
            if dp[i - coin] + 1 < dp[i]:
                dp[i] = dp[i - coin] + 1

    print("dp table:", dp)
    return dp[amount] if dp[amount] != float('inf') else -1

coin_change_verbose([1, 2, 5], 6)
# dp table: [0, 1, 1, 2, 2, 1, 2]
# dp[6] = 2 means: 5 + 1 = 2 coins

def coin_change_with_coins(coins, amount):
    """Return (min_coins, coin_list) or (-1, []) if impossible."""
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    used = [-1] * (amount + 1)   # stores the coin used to reach each amount

    for coin in coins:
        for i in range(coin, amount + 1):
            if dp[i - coin] + 1 < dp[i]:
                dp[i] = dp[i - coin] + 1
                used[i] = coin

    if dp[amount] == float('inf'):
        return -1, []

    # Backtrack through `used` to find the actual coins
    result_coins = []
    remaining = amount
    while remaining > 0:
        result_coins.append(used[remaining])
        remaining -= used[remaining]

    return dp[amount], result_coins

count, coins_used = coin_change_with_coins([1, 3, 4], 6)
print(f"Min coins: {count}, Coins: {coins_used}")
# Output: Min coins: 2, Coins: [3, 3]

def coin_change_ways(coins, amount):
    """Return the number of distinct ways to make `amount`."""
    dp = [0] * (amount + 1)
    dp[0] = 1   # one way to make 0: use no coins

    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]

    return dp[amount]

print(coin_change_ways([1, 2, 5], 5))
# Output: 4  (5), (2+2+1), (2+1+1+1), (1+1+1+1+1)