Coin change problem

Tags: ,

Given a number S and coins of values V = {v1, v2,v3, v4}. Find the number of ways change can be made for S using these coins.We have an infinite supply of these coins. Commonly, this problem is known as the coin change problem. For example,

Input:
N = 4; S = {1,2,3}
Output:
4
Explanation:
There are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}

coin-change-problem

Thoughts

As always, let’s start with a brute force solution. We have two choices for a coin: Either we can include the coin in solution, or we can not include it in solution. If coin m is included in solution, problem reduces to find change for value N-V(m) using K coins. Notice that we can again use all the coins for the reduced problems too.
If a coin is not included in a solution when the value to change is less than the denomination of the coin. At this time, there is a reduction in value to be changed, but we lose one coin, hence problem stands: Change value V with N-1 coins.
If we look at it, it is simple recursive formulation.

C(N,m) = C(N,m-1) + C(N- V(m), m)

coin change problem

When do we stop then? When do we know that there is no more solution going forward? If change is required for value zero, there is only one solution possible, which is to include no coin.

C(N,m) = 1 if N == 0

Also, what is the solution if we do not have any coins with us at all and there is value to be changed. There is no solution then.

C(N,m) =0 if N > 0 and m < 0

Also, if the value required is less than zero, then there is again no solution, given that all coins have positive values.

C(N,m) = 0 if N < 0

We see that problem reduces to smaller problems and then there are points when we can stop going forward. That’s a perfect condition for a recursive solution.

Recursive implementation

package com.company;

/**
 * Created by sangar on 5.5.18.
 */
public class CoinChange {

    public static int coinChange(int value, int[] coins, int consideredCoin){
        /* If the value to be changed is negative, since coins are positives,
        there is no way to change them
         */
        if(value < 0) return 0;

        /*When there may or may not be coins, and no value is
        required, there is one solution which is not to include any
        coin */
        if(value == 0) return 1;

        /* When there is the value required by no coins left,
           there is no solution
         */
        if(value > 0 && consideredCoin == coins.length) return 0;
                // When coin is included
        return coinChange(value-coins[consideredCoin],coins, consideredCoin)
               //When coin is not included
            + coinChange(value,coins, consideredCoin + 1);
    }

    public  static void main(String[] args){
        int value = 4;
        int[] coins = {1,2,3};

        int count = coinChange(value, coins, 0);
        System.out.println(count);
    }
}

Complexity of recursive implementation of coin change solution is exponential O(2m) where m is number of coins.

For every coin, we have 2 options, either we include it or exclude it so if we think in terms of binary, its 0(exclude) or 1(include). so for example if we have 2 coins, options will be [ 00, 01, 10, 11 ]. so its 22. For m coins, it will be 2m. In all these options we will be checking whether that selection has made the change which is required
The reason for this exponential complexity is that we are calculating smaller subproblems again and again.

coin change problem recursive tree

In the discussion so far, we see two properties of the solution: First, there is an optimal substructure, which is an optimal solution to subproblems provides an optimal solution to bigger problems. This is known as the optimal substructure property. Second, subproblems are overlapping. These two conditions as necessary for applying a dynamic programming approach.

To avoid calculating the same subproblem again and again, that we can avoid using simple memorization. Let’s create a two-dimensional table Coins. Coins(i, j) represents the number of ways in which change for i can be made using j coins.
Now if jth coin is included, then numbers of ways will be Coins(i- v[j], j-1)

If jth coin is not included, number of ways will be  Coins (i, j-1). Adding both of them will give us

Coins(i,j) = Coins(i-v[j]) + Coins(i, j-1).

For all i = 0 Cost(i,j) = 1, for all j = 0 Cost(i,j) will 1 for all i > 0.
We can start bottom-up and fill the table as per the formula above. Once we have filled the entire table, Coins(N,m) will be answered to the problem.

Show me the dynamic programming implementation

package com.company;

/**
 * Created by sangar on 5.5.18.
 */
public class CoinChange {

    public static int coinChangeDP(int value, int[] coins){

        int[][] numWays = new int[value+1][coins.length+1];

        for(int i = 0; i <= coins.length; i++ ){
            numWays[0][i] = 1;
        }

        for(int i = 1; i <= value; i++ ){
            numWays[i][0] = 0;
        }

        for(int i = 1; i <= value; i++){
            for(int j = 1; j <= coins.length; j++){
                numWays[i][j] = (i -coins[j-1] >= 0 ? numWays[i-coins[j-1]][j] : 0 )
                                 + numWays[i][j-1];
            }
        }

        return numWays[value][coins.length];
    }

    public  static void main(String[] args){
        int value = 4;
        int[] coins = {1,2,3};

        int count = coinChangeDP(value, coins);

        System.out.println(count);
    }
}

Example: for Value = 4 and coins {1,2,3}, below is the bottom up filling of table.

The complexity of dynamic programming implementation of the coin change problem is O(Nm) where N is value and m is the number of coins. Additional O(Nm) space is also required for memoization.

Please share if there is something missing or wrong. If you want to share your knowledge with thousands of learners across the world, please reach out to us on [email protected]