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.
1function coinChange(coins, amount) {
2 let dp = Array(amount + 1).fill(Infinity);
3 dp[0] = 0;
4 for (let i = 1; i <= amount; i++) {
5 for (let coin of coins) {
6 if (coin <= i) {
7 dp[i] = Math.min(dp[i], dp[i - coin] + 1);
8 }
9 }
10 }
11 return dp[amount] === Infinity ? -1 : dp[amount];
12}
13
14const coins = [1, 2, 5];
15const amount = 11;
16console.log(coinChange(coins, amount));In this JavaScript solution, an array dp tracks the minimum coins needed for each value up to amount. The array initializes all but dp[0] to Infinity. By iterating amounts and coins, the algorithm updates dp[i] to engage the smallest countermove possible.
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.