To solve this problem, we can use a dynamic programming approach. We will create an array dp of size amount + 1, where dp[i] represents the fewest number of coins needed to make up the amount i.

First, we initialize all elements of dp to infinity, except for dp[0] which is set to 0, since we don't need any coins to make up an amount of 0.

Then, for each coin in the coins array, we iterate through the dp array from the value of the coin up to the amount. For each value j, we update dp[j] to be the minimum of dp[j] and dp[j - coin] + 1. This means that we are considering using the current coin to make up the amount j, and we take the minimum of the previous number of coins needed for amount j and the number of coins needed for amount j - coin plus one more coin.

Finally, if dp[amount] is still infinity, it means that it is not possible to make up the amount using the given coins, so we return -1. Otherwise, we return dp[amount] as the fewest number of coins needed.

Here is the implementation in Python:

def coinChange(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0

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

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

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

coins = [2]
amount = 3
print(coinChange(coins, amount)) # Output: -1

coins = [1]
amount = 0
print(coinChange(coins, amount)) # Output: 0

The time complexity of this solution is O(amount * n), where n is the number of coins, and the space complexity is O(amount).

Question

To solve this problem, we can use a dynamic programming approach. We will create an array dp of size amount + 1, where dp[i] represents the fewest number of coins needed to make up the amount i.

First, we initialize all elements of dp to infinity, except for dp[0] which is set to 0, since we don't need any coins to make up an amount of 0.

Then, for each coin in the coins array, we iterate through the dp array from the value of the coin up to the amount. For each value j, we update dp[j] to be the minimum of dp[j] and dp[j - coin] + 1. This means that we are considering using the current coin to make up the amount j, and we take the minimum of the previous number of coins needed for amount j and the number of coins needed for amount j - coin plus one more coin.

Finally, if dp[amount] is still infinity, it means that it is not possible to make up the amount using the given coins, so we return -1. Otherwise, we return dp[amount] as the fewest number of coins needed.

Here is the implementation in Python:

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    
    for coin in coins:
        for j in range(coin, amount + 1):
            dp[j] = min(dp[j], dp[j - coin] + 1)
    
    if dp[amount] == float('inf'):
        return -1
    else:
        return dp[amount]

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

coins = [2]
amount = 3
print(coinChange(coins, amount))  # Output: -1

coins = [1]
amount = 0
print(coinChange(coins, amount))  # Output: 0

The time complexity of this solution is O(amount * n), where n is the number of coins, and the space complexity is O(amount).

Knowee AI · Accepted Answer