Minimum Coins to Make Change

Given a value V cents, and an array of coin denominations coins = [C_0, C_1, ..., C_m-1]. Find the minimum number of coins required to make change for V. If it is not possible to make change, return -1.

This problem is a variation of the Coin Change Problem. Instead of finding the total number of combinations, we want to find the optimal combination that minimizes the coin count.

Examples

Example 1

Input coins: [25, 10, 5]
Target Value (V): 30
Output: 2
Explanation: We can use one coin of 25 cents and one coin of 5 cents (25 + 5 = 30).

Example 2

Input coins: [9, 6, 5, 1]
Target Value (V): 11
Output: 2
Explanation: We can use one coin of 6 cents and one coin of 5 cents (6 + 5 = 11).

Mathematical Substructure

Let minCoins(V) be the minimum number of coins required to make change for value V.

If V === 0, then 0 coins are required.
If V > 0, minCoins(V) = min(1 + minCoins(V - coins[i])) for all 0 <= i < m where coins[i] <= V.

1. Recursive Solution (Naive)

function minCoinsRecursive(coins, m, V) {
    // Base Case
    if (V === 0) return 0;
 
    let res = Infinity;
 
    // Try every coin that has smaller value than V
    for (let i = 0; i < m; i++) {
        if (coins[i] <= V) {
            let sub_res = minCoinsRecursive(coins, m, V - coins[i]);
 
            // Check for Infinity to avoid overflow and see if the result can be minimized
            if (sub_res !== Infinity && sub_res + 1 < res) {
                res = sub_res + 1;
            }
        }
    }
 
    return res;
}

2. Tabulation Solution (Bottom-Up DP)

We construct a 1D table dp of size V + 1.

function minCoinsTabulation(coins, m, V) {
    // dp[i] will store the minimum number of coins required for value i
    const dp = new Array(V + 1).fill(Infinity);
 
    // Base case: 0 coins needed for value 0
    dp[0] = 0;
 
    // Compute minimum coins for all values from 1 to V
    for (let i = 1; i <= V; i++) {
        // Go through all coins smaller than or equal to i
        for (let j = 0; j < m; j++) {
            if (coins[j] <= i) {
                let sub_res = dp[i - coins[j]];
                if (sub_res !== Infinity && sub_res + 1 < dp[i]) {
                    dp[i] = sub_res + 1;
                }
            }
        }
    }
 
    return dp[V] === Infinity ? -1 : dp[V];
}
 
// Driver code
const coins = [9, 6, 5, 1];
const V = 11;
console.log("Minimum coins required:", minCoinsTabulation(coins, coins.length, V));
// Output: Minimum coins required: 2

Complexity Analysis

Time Complexity: O(M * V)
- Where M is the number of coin denominations and V is the target value.
Space Complexity: O(V)
- To store the 1D DP table.

0-1 Knapsack Min Jumps to Reach End