UVa 674

From Algorithmist
Jump to navigation Jump to search

Problem Number - Coin Change[edit]

Summary[edit]

Suppose there are 5 types of coins: 50-cent, 25-cent, 10-cent, 5-cent, and 1-cent. We want to make changes with these coins for a given amount of money.

Write a program to find the total number of different ways of making changes for any amount of money in cents. Your program should be able to handle up to 7489 cents.

Explanation[edit]

Gotchas[edit]

Notes[edit]

It is possible within the time limit to fully populate a matrix of all possible answers and then simply output value corresponding to the input.

Implementations[edit]

The high-values are computationally expensive, but can be accelerated using Dynamic Programming.

Optimizations[edit]

Input[edit]

11
26

Output[edit]

4
13

Solution[edit]

References[edit]