Coin Change medium

Problem Statement

You are 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.

You may assume that you have an infinite number of each kind of coin.

Example 1:

Input: coins = [1, 2, 5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3 Output: -1

Steps:

1. Initialization: Create a DP table dp of size amount + 1, where dp[i] represents the minimum number of coins needed to make up amount i. Initialize dp[0] = 0 (0 coins needed to make amount 0) and the rest to float('inf') (representing infinity, meaning it's currently unreachable).

2. Iteration: Iterate through each coin c in coins. For each coin, iterate through the DP table from c to amount. For each amount i, check if using coin c can improve the minimum number of coins needed. If dp[i - c] + 1 < dp[i], it means using coin c and the minimum number of coins needed for i - c is better than the current minimum for i. Update dp[i] accordingly.

3. Result: After iterating through all coins, dp[amount] will contain the minimum number of coins needed to make up the amount. If dp[amount] is still float('inf'), it means the amount is unreachable, so return -1. Otherwise, return dp[amount].

Explanation:

This solution uses dynamic programming to efficiently find the minimum number of coins. The DP table stores the minimum number of coins for each amount from 0 up to the target amount. By iterating through the coins and updating the DP table, we progressively find the optimal solution. Each entry dp[i] is updated by considering whether adding a given coin c leads to a smaller number of coins to reach i than previously known.

Code:

def coinChange(coins, amount):
    """
    :type coins: List[int]
    :type amount: int
    :rtype: int
    """
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

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

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

Complexity:

• Time Complexity: O(amount * len(coins)). The nested loops iterate through the DP table and coins.
• Space Complexity: O(amount). The DP table uses space proportional to the amount.