Number of ways to change coins with given value | Dynmaic Programming

Coin change is a classical dynamic programming problem to count the number of possible ways to get value V cents using list of denomination of n coins.

For example :

List of coin denomination : centsValue[] = 1, 5, 10, 25, 50

For value 5, there 2 possible ways to change coins : {1 + 1 + 1 + 1 + 1, 5}

Solution:
First we need to find the recurrence relation. ways(index, value), where value is the remaining amount of cents that we need to change. and the first parameter index is index of the coin type. Lets consider all cases :

  1. ways(index, 0) = 1 // There is only 1 way i.e choose nothing.
  2. ways(index, <0) = 0 // We cannot change negative value.
  3. ways(n, value) = 0 // We have considered all coins from {0…n-1} and reached index = n
  4. ways(index, value) = ways(index, value – centsValue[index]) + ways (index + 1, value) // use coin with index + ignore coin with index type.

Call ways(0,V) to get answer.

Here is the iterative solution:

// for zero value choose nothing.
ways[index][0] = 1 

// for all index from {0...n-1}
ways[index][value] = ways[index][value-centsValue[index]] + ways[index-1][value] 

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
long long int ways[5][30001];

int main()
{
	memset(ways, 0, sizeof(ways));
	
	long long int cents[5] = {1,5,10,25,50};
	//Solve initially ways array;
	for(long long int i = 0 ; i < 5; i++)
	{
		ways[i][0] = 1;
	}
	for(long long int i = 0 ; i < 5; i++)
	{
		for(long long int j = 1; j<=30000; j++)
		{
			// consider coin with index i
			ways[i][j] = (j-cents[i] >=0) ? ways[i][j-cents[i]] : 0;
			// skip coin with index i and consider previous coins
			ways[i][j] += (i-1>=0) ? ways[i-1][j] : 0;
		}
	}
	// For value 5
	cout<<ways[4][5]<<endl;
	//for value 50
	cout<<ways[4][50]<<endl;
	//for value 29999
	cout<<ways[4][29999]<<endl;
	return 0;
}

Site Footer