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.
1using System;
2
3public class Solution {
4 public int CoinChange(int[] coins, int amount) {
5 int[] dp = new int[amount + 1];
6 Array.Fill(dp, int.MaxValue);
7 dp[0] = 0;
8 for (int i = 1; i <= amount; i++) {
9 foreach (int coin in coins) {
10 if (coin <= i && dp[i - coin] != int.MaxValue) {
11 dp[i] = Math.Min(dp[i], dp[i - coin] + 1);
12 }
13 }
14 }
15 return dp[amount] == int.MaxValue ? -1 : dp[amount];
16 }
17 public static void Main(string[] args) {
18 int[] coins = {1, 2, 5};
19 int amount = 11;
20 Solution solution = new Solution();
21 Console.WriteLine(solution.CoinChange(coins, amount));
22 }
23}This C# solution declares an array dp initialized to containing int.MaxValue for each element, where zero coins are needed to form amount zero. Iterating through each potential amount, the array is updated to reflect the minimum number of coins needed by considering each coin in turn. If dp[amount] remains as int.MaxValue, return -1; otherwise, return the value in dp[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.