Coin Change - Leetcode Solution

The Coin Change problem on LeetCode is a classic dynamic programming problem where we are given a set of coins and a target amount to reach with those coins. The problem statement is as follows:

You are given coins of different denominations and a total amount of money amount. Write a function to compute 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.

For example, given coins = [1, 2, 5] and amount = 11, the function should return 3 (11 = 5 + 5 + 1).

One way to approach this problem is to use dynamic programming. We can create an array dp where dp[i] represents the minimum number of coins needed to make up the amount i.

We can start by initializing dp[0] to 0, since it takes zero coins to make up an amount of zero. Then for each amount i from 1 to the target amount, we can iterate over all the coins less than or equal to i and consider two possibilities:

1. We can use the coin to make up the amount i. In this case, we need to find the minimum number of coins needed to make up the remaining amount (i - coin). Since we are looking for the minimum number of coins, we can take the minimum of dp[i] and dp[i - coin] + 1.

2. We cannot use the coin to make up the amount i. In this case, we do not need to do anything as dp[i] remains the same.

We can continue this process for all amounts from 1 to the target amount, and the final result will be stored in dp[amount]. If there is no combination of coins that can make up the amount, then dp[amount] will remain at its initial value of infinity, and we can return -1 in this case.

Here's the implementation of the above algorithm in Python:

def coinChange(coins, amount):
    # Initialize dp array with infinity
    dp = [float('inf') for _ in range(amount + 1)]
    # Base case: zero coins are needed to make amount 0
    dp[0] = 0
    # Iterate over all amounts from 1 to target amount
    for i in range(1, amount + 1):
        # Iterate over all coins less than or equal to i
        for coin in coins:
            # Check if coin can be used to make up amount i
            if coin <= i:
                # Take minimum of using coin and not using coin
                dp[i] = min(dp[i], dp[i - coin] + 1)
    # If amount cannot be made up by any combination of coins, return -1
    if dp[amount] == float('inf'):
        return -1
    else:
        return dp[amount]

The time complexity of the above algorithm is O(amount * n), where n is the number of coins, since we are iterating over all amounts and all coins less than or equal to each amount. The space complexity is O(amount) since we are using dp array of size amount + 1.

Overall, this algorithm provides an efficient solution to the Coin Change problem with the time complexity dependent only on the size of the input.

1