This approach dynamically computes the fewest number of coins needed for each amount from 0 to the target amount. You initialize an array dp where dp[i] represents the fewest number of coins needed to form amount i. Start with dp[0] = 0 since zero coins are needed to make the amount zero. For other amounts, assume infinity until proven otherwise. Iterate through each amount up to amount and each coin, updating dp accordingly. The solution lies in dp[amount].
Time Complexity: O(n * m), where n is the amount and m is the number of coins.
Space Complexity: O(n), for the array dp.
1def coinChange(coins, amount):
2 dp = [float('inf')] * (amount + 1)
3 dp[0] = 0
4 for i in range(1, amount + 1):
5 for coin in coins:
6 if coin <= i:
7 dp[i] = min(dp[i], dp[i - coin] + 1)
8 return dp[amount] if dp[amount] != float('inf') else -1
9
10coins = [1, 2, 5]
11amount = 11
12print(coinChange(coins, amount))This Python solution constructs a list, dp, to store the minimum number of coins required to form each amount up to amount. Each value is initiated to float('inf') except for the zero amount which is zero. It iteratively updates possible amounts by considering each coin and updates the dp values accordingly to ensure the minimum is found.
This BFS-based method considers each step as a level, ensuring that every level in the search tree corresponds to adding a different coin denomination yielding a new amount. It is implemented using a queue initialized with the target amount, repeatedly generating the next possible amounts by subtracting each coin in turn until the amount is zero or deemed unreachable.
Time Complexity: Approximately O(n * m), comparable to standard BFS, where n is the amount and m is the number of coins. Actual time can be higher based on processed nodes.
Space Complexity: O(n), limited by queue and visited set sizes, corresponding to different amounts explored.
1from collections import deque
2
3def coinChange(coins, amount):
4 if amount == 0:
5 return 0
6 queue = deque([(amount, 0)])
7 visited = set()
8 while queue:
9 current, steps = queue.popleft()
10 for coin in coins:
11 next_amount = current - coin
12 if next_amount == 0:
13 return steps + 1
14 if next_amount > 0 and next_amount not in visited:
15 visited.add(next_amount)
16 queue.append((next_amount, steps + 1))
17 return -1
18
19coins = [1, 2, 5]
20amount = 11
21print(coinChange(coins, amount))This BFS solution uses a queue to attempt each feasible coin subtraction on a given amount. It initially pushes a pair into the queue: the current amount, and the number of steps (or coins) taken. The iteration through coins short-circuits when next_amount becomes zero, else it appends the resulting amounts — not yet checked — back into the queue.