Trusted answers to developer questions

Educative Answers Team

This version of the **coin change problem** deals with finding the total number of ways that an amount of money can be made using specific coins *only*.

For example, if 10 cents are needed, and you can only use coins of the amounts 2,5, and 8; then 10 cents can be created in exactly three ways: {2, 2, 2, 2, 2}, {5, 5} and {2, 8}.

Since this problem is solved using *Dynamic Programming (DP)*, the solutions to the sub-problems must be utilized to reach the original problem’s solution – a two-dimensional array will store the sub-problems’ solutions.

Below is the solution to this version of the coin change problem:

- If the highest coin does not exceed the required sum, then the number of ways that the sum can be made will be equal to
*the number of ways that the same sum can be made without the highest coin**+**the number of ways in which a value of*.`sum - highest coin`

can be made - Else, if the highest coin exceeds the required sum, then the number of ways this sum can be made is equal to
*the number of ways it could be made without this coin*.

A 2-D array (`arr`

) will be used in this solution. A 1-D array may be used as well, but the following explanation cannot be applied to it:

The value at `arr[i][j]`

represents the number of possible ways that the sum `j`

can be made using the first `i`

coins *only*.

#include <iostream> using namespace std; int findPossibleWays(int coins[], int sum, int size){ // Declaring a 2-D array // for storing solutions to subproblems: int **arr = new int*[size + 1]; for(int i = 0; i < size + 1; i++) arr[i] = new int[sum + 1]; // Initializing first column of array to 1 // because a sum of 0 can be made // in one possible way: {0} for(int i = 0; i < size + 1; i++) arr[i][0] = 1; // Initializing first row of array to 0 // because a sum cannot be made with no coins: for(int j = 0; j < sum + 1; j++) arr[0][j] = 0; // Applying the recursive solution: for(int i = 1; i < size + 1; i++) for(int j = 1; j < sum + 1; j++) if(coins[i - 1] > j) arr[i][j] = arr[i - 1][j]; else arr[i][j] = arr[i - 1][j] + arr[i][j - coins[i - 1]]; int answer = arr[size][sum]; // Freeing memory from heap: for(int i = 0; i < size + 1; i++) delete[] arr[i]; delete[] arr; return answer; } int main(){ // Declaring array of available coins: int coins[] = {1, 2}; int size = sizeof(coins) / sizeof(coins[0]); // The sum to be made: int sum = 5; cout << "Number of possible ways in which " << sum << " can be made is " << findPossibleWays(coins, sum, size) << endl; return 0; }

RELATED TAGS

problem

coin

change

memoization

Copyright ©2022 Educative, Inc. All rights reserved

RELATED COURSES

View all Courses

Keep Exploring

Related Courses