Coin change problem with dynamic programming

Coin change problem using dynamic programming

Given a number S and coins of values V = {V1,V2,V3, V4}. Find number of ways change can be made for S using these coins.We have infinite supply of these coins. For example,
S = 4, V = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}

Mathematically, we have to find number of solutions for following expression:
S = summation (k = 1 to m ) X(K) * V(K)

Here X(K) cannot be negative. We have solved similar problem in subset sum problem. Refer :Subset sum problem

There we have limitation that every element can be considered only once (there was no infinite supply)when while formulating the solution. So we were reducing the size of input every time we considered an element. However in our case we don’t need to decrease the size of the input as we have infinite supply of coins. We decrease the count only when there is no possibility of it being included further in solution.

Other difference is that subset problem was a decision problem where we need to say True or False for answer, here we need to give count.Rest all remains same.
So, with each coin there are two possibilities associated :

1. Either the coin is included in solution.
2. Or it is not included in solution.

If coin is included in solution, our problem of making change with coins reduces to find solution for N-V(m) using K coins. See we can again use the same coin in reduced problem.

If coin is not included in solution, and since coins given are in sorted order, it will never be included into solution, so just decrease the coins set by 1 and keep the required sum as N.

If we look at it, it is simple recursive formulation.

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

What will be base condition then?
If with any number of coins we reach where change is required for 0, we have found one solution. i.e

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

What if we have considered all coins and N is still greater than 0, in that case combination we have considered does not provide a solution. Hence,

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

What if sum required at a point is less than zero, that is we have included extra coins and that combination is not a solution. Hence,

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

Coin change problem implementation

int coins(int values[], int N, int m){

    if(N == 0) return 1;
    if(N<0) return 0;
    if(N>0 && m<0) return 0;

    return coins(values, N, m-1) + coins(values, N-values[m], m);
}

//Driver program
int main(){
    int N= 10;
    int values[] = {2,3, 5,6};
    printf("\n%d", coins(values, N, 3) );
    return 0;
}

We can see that we are calculating the same sub problem again and again, that we can avoid using simple memorization.

Let’s say Coins(i, j) represents the number of ways in which change for i can be made using j coins. Now if the jth item 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). 
int coinsChangeProblem(int values[], int N, int m){

    int table[N+1][m+1];
    int include, exclude;
    for(int i=0; i<=m; i++){
        table[0][i]=1;
    }

    for(int i=1; i<=N; i++){
        for(int j=0; j<=m; j++){
            include = (i-values[j]>=0)? table[i-values[j]][j]: 0;
            exclude = (j>=1)? table[i][j-1]:0;
            table[i][j] = include + exclude;
        }
    }
    return table[N][m];
}
/Driver program
int main(){
    int N= 10;
    int values[] = {2,3, 5,6};
    printf("\n%d", coinsChangeProblem(values, N, 3) );
    return 0;
}

Complexity of coin change problem of recursive code will be exponential while of that of dynamic programming approach will be O(N2)

Please share if there is something wrong or missing. If you want to contribute to website or have an interview experience to share, please contact us.