Scribd
Upload
3 views1 page

Coin Change Problem Solution Code

The document contains a C++ code implementation for solving the coin change problem using dynamic programming. It initializes a dp array to count combinations of coins for values up to 7500, iterating through predefined coin denominations. The program reads an integer input and outputs the number of ways to make that amount using the available coins.

Uploaded by

Poon Ting Kwok
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views1 page

Coin Change Problem Solution Code

The document contains a C++ code implementation for solving the coin change problem using dynamic programming. It initializes a dp array to count combinations of coins for values up to 7500, iterating through predefined coin denominations. The program reads an integer input and outputs the number of ways to make that amount using the available coins.

Uploaded by

Poon Ting Kwok
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

This is a code to solve the coin change problem. I would like to share it.

#include <iostream>
#include <cstring>
using namespace std;
int n, i, j;
int dp[7500];
int coins[5] = { 1, 5, 10, 25, 50 };

int main()
{
// removed unnecessary recursion and array in here.
memset(dp, 0, sizeof(dp));
dp[0] = 1;
for (int i = 0; i < 5; i++) {
for (int j = coins[i]; j < 7500; j++) {
dp[j] += dp[j - coins[i]];
}
}
while (cin >> n)
{
cout << dp[n] << endl;
}
return 0;
}

You might also like