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.
1#include <stdio.h>
2#include <limits.h>
3
4int coinChange(int* coins, int coinsSize, int amount) {
5 int dp[amount + 1];
6 for (int i = 0; i <= amount; i++) dp[i] = INT_MAX;
7 dp[0] = 0;
8 for (int i = 1; i <= amount; i++) {
9 for (int j = 0; j < coinsSize; j++) {
10 if (coins[j] <= i && dp[i - coins[j]] != INT_MAX) {
11 dp[i] = dp[i] < (dp[i - coins[j]] + 1) ? dp[i] : (dp[i - coins[j]] + 1);
12 }
13 }
14 }
15 return dp[amount] == INT_MAX ? -1 : dp[amount];
16}
17
18int main() {
19 int coins[] = {1, 2, 5};
20 int amount = 11;
21 printf("%d\n", coinChange(coins, 3, amount));
22 return 0;
23}This C solution uses an array dp initialized to INT_MAX except for dp[0] which is 0, signifying no coins are needed to make zero amount. For each possible amount, we iterate through each coin, updating dp[i] to be the minimum number of coins found so far that can make up i. The answer is dp[amount] unless it remains as infinity (in which case it is impossible to form the amount).
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.