Given infinite supply of 25 cents, 10 cents, 5 cents, and 1 cent. Find the number of ways of representing n cents. (The order doesn’t matter). This is a coin change problem and will require the implementation of Dynamic Programming.

Ex: n = 10 => {1,1,1,1,1,1,1,1,1,1} {1,1,1,1,1,5} {5,5} {10}

#### Algorithm:

We are given a set of 4 Coins of type 1 cents, 5 cents, 10 cents, 25 cents. To find the number of ways of making n cents using these 4 cents, we will consider 2 conditions:

- Try to make n cents by including the i
*th*cent from the set of 4 coins. number_of_ways(n-coin_arr[m], coin_arr m);*here m in the number of coins in given set(here m=4).* - Try to make n cents by not including the i
*th*cent from the given set of the 4 coins. number_of_ways(n, coin_arr, m-1);

This problem involves the repetition of subproblems, so we will use Dynamic Programming.

#### Implementation of the above code in CPP

###### Recursive Approach

Iterative Approach

Output

Coins Output n = 5 2 n = 26 13 n = 1000 142511

#### Time Complexity

Since we have used Dynamic Programming here, hence the time complexity of the above program for coin change problem is **O(NM)**, N the total cents to make and M is the number of the coin in a given set.