Coin change - DP

"""
Given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money, return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

This implementation ensures that the problem is solved in a time-efficient manner using dynamic programming, with a time complexity of O(amount * n) where n is the number of different coins.
"""

def coinChange(coins, amount):
    # Initialize DP array with a large number, amount + 1 is a safe large number since we can't use more than amount coins.
    dp = [amount + 1] * (amount + 1)

    # Base case: to make 0 amount, 0 coins are needed
    dp[0] = 0

    # Loop through each amount from 1 to amount
    for a in range(1, amount + 1):
        # Loop through each coin
        for coin in coins:
            if a - coin >= 0:
                dp[a] = min(dp[a], dp[a - coin] + 1)

    # If dp[amount] is still amount + 1, it means it's not possible to form that amount
    return dp[amount] if dp[amount] != amount + 1 else -1

# Example usage
coins = [1, 2, 5]
amount = 11
print(coinChange(coins, amount))  # Output: 3 (11 = 5 + 5 + 1)