coin-change-test.js

/**
 * Problem: Coin Change (Leetcode #322)
 *
 * You are given an array of coin denominations `coins` and an integer `amount`.
 * Return the **fewest number of coins** needed to make up that amount.
 *
 * If it's not possible, return -1.
 *
 * You may use **each coin unlimited times** (unbounded knapsack).
 *
 * Example:
 * Input: coins = [1, 2, 5], amount = 11
 * Output: 3  // (5 + 5 + 1)
 *
 * Use bottom-up dynamic programming to solve efficiently.
 */

function coinChange(coins, amount) {
    // 1. Create a dp array of size (amount + 1), initialized to Infinity
    // 2. dp[0] = 0 → base case: 0 coins to make amount 0
    // 3. For each coin:
    //    a. Loop from coin value up to amount
    //    b. Update dp[i] = min(dp[i], dp[i - coin] + 1)
    // 4. Return dp[amount] if not Infinity, else return -1
}