Coin Change Problem

1function coinChange(coins, amount) {
2  // dp[i] stores the minimum number of coins needed for sub-amount i
3  const dp = new Array(amount + 1).fill(Infinity);
4  dp[0] = 0; // Base case: 0 coins needed for amount 0
5 
6  // Build DP table from 1 to amount
7  for (let i = 1; i <= amount; i++) {
8    for (const coin of coins) {
9      if (i - coin >= 0 && dp[i - coin] !== Infinity) {
10        dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
11      }
12    }
13  }
14 
15  return dp[amount] === Infinity ? -1 : dp[amount];
16}
17 
18// Example usage:
19// coinChange([1, 2, 5], 11); // 3 (5 + 5 + 1)
20// coinChange([2], 3);        // -1 (Impossible)
21// coinChange([1, 3, 4], 6);  // 2 (3 + 3, beats greedy 4 + 1 + 1)