Coin Change Problem

Minimum Number of Coins Problem

Given a variety of coin types defining a currency system, find the minimum number of coins required to express a given amount of money. Assume infinite supply of coins of every type. 

Example

Input: Coin types: [1, 3, 5]. Amount to express: 9.

Output: 3

Here are all the unique ways to express 9 as a sum of coins 1, 3 and 5:

1, 1, 1, 1, 1, 1, 1, 1, 1

1, 1, 1, 1, 1, 1, 3

1, 1, 1, 1, 5

1, 1, 1, 3, 3

1, 3, 5

3, 3, 3

Last two ways use the minimal number of coins, 3.

Notes:

Every input will include a coin of value 1. This guarantees that a solution will always exist.

There will be no duplicate coin types in the input.

Constraints:

● 1 <= number of coin types <= 100

● 1 <= coin value <= 100

● 1 <= amount of money to express <= 10000

Solutions

We've provided two solutions.

1) brute_force_solution.cpp

We will follow the following recursive definition:

     If value == 0:

             // Zero coins are required to express the value of 0.

             // End of recursion. Base case.

             return 0

     If value > 0:

             minimum_coins(value) = min {1 + minimum_coins(value-coins[i])} (where i belongs to [0,n-1] and coins[i] <= value)

Basically what we are doing here is exhaustively searching for all the possible combinations of denominations which can generate our desired value and maintain a minimum number of coins required to generate that value and that will be our answer.

This method is not efficient as it computes subproblems again and again.

Time Complexity:

O(n^value).

Auxiliary Space Used:

O(value). That’s the maximum number of the recursive calls at a time.

Space Complexity:

O(n + value).

Input takes O(n) and the auxiliary space used is O(value).

int minimum_coins(vector &coins, int value) {
    // If value is zero return 0.
    if (value == 0) {
        return 0;
    }
    // Maximum value assigned initially
    int global_min=100005;
    for(int i=0; i < coins.size(); i++){
        if (coins[i] <= value) {
            // To find minimum coins required to make remaining value-coins[i]
            int local_min=minimum_coins(coins, value-coins[i]);
            // local_min number of coins required to make remaining value-coins[i] and 
            // 1 coin with value coins[i] used.
            if (local_min+1 < global_min) {
                global_min=local_min+1;
            }
        }
    }
    // Return maintained global minimum value
    return global_min; 
}

2) optimal_solution.cpp

It is fairly intuitive that the brute force method computes subproblems again and again, so we need to cache the data.

It can be easily done using the bottom-up DP approach. We will use a one-dimensional array as a DP table which at the i-th index stores the minimum number of coins required to value the value i.

Base case: dp[0]=0, other values in the array are set to the positive infinity.

We use 2 loops:

The 1st loop(i) iterates over 1..value.

The 2nd loop(j) iterates over the given coin types.

For every value of i and coins[j] we check if that i (current value to be expressed) is greater than or equals to the coin value, i.e. i>=coins[j]. If yes, then we update dp[i] = min(dp[i],1+dp[i-coins[j]]).

After the dp table has been constructed, dp[value] will

give us our answer.

Time Complexity:

O(n*value).

The outer loop makes value iterations and the inner one makes n iterations.

Auxiliary Space Used:

O(value).

The size of the dp array.

Space Complexity:

O(n + value).

Input takes O(n) and the auxiliary space used is O(value).

const int MAX_VALUE=100005;
int minimum_coins(vector coins, int value) {
    // Dp array of size (value+1) and pre filled value MAX_VALUE
    vector dp(value+1, MAX_VALUE);
    // As number of coins required to make 0 value is 0
    dp[0]=0;
    // Following nested loop calculates the minimum number of coins 
    // required to make the value i and stored in dp table
    int n=coins.size();
    for(int i=1; i <= value; i++) {
        for(int j=0; j < n; j++) {
            if (i >= coins[j] and 1+dp[i-coins[j]] < dp[i]) {
                // Condition that we have found a better minimal solution
                dp[i]=1+dp[i-coins[j]];
            }
        }
    }
    // Recursive function that calculates the distinct combinations of minimal size
    // that has the sum given to the input value
    return dp[value];
}