thefourtheye's weblog

opinions are my own; try code/suggestions at your own risk

Number of Ways to Change Making (Dynamic Programming)

| Comments

This is a variant of change making problem. Here, we are just asked to count the number of ways to make the specific change. With a little change to the change making problem's solution, we can solve this one. The problems which can be solved with the following solution are
UVa - 657 - Coin Change

UVa - 357 - Let Me Count The Ways (Need to change the way solution is printed as per problem description)

# include <iostream>
# include <cstdio>
using namespace std;
unsigned long long NumberOfWays [30001], Coins []= {1, 5, 10, 25, 50}, Num;
int main ()
{
//freopen ("Input.txt", "r", stdin);
//freopen ("Scratch.txt", "w", stdout);
NumberOfWays[0] = 1;
for (int i = 0; i < 5; i++)
for (int j = Coins[i]; j < 30001; j++)
NumberOfWays [j] += NumberOfWays [j - Coins[i]];
while (scanf ("%lld", &Num) != EOF)
printf ("%lld\n", NumberOfWays[Num]); //Change this for UVa - 357 - Let Me Count The Ways
}