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 :

- ways(index, 0) = 1 // There is only 1 way i.e choose nothing.
- ways(index, <0) = 0 // We cannot change negative value.
- ways(n, value) = 0 // We have considered all coins from {0…n-1} and reached index = n
- 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; }