# UVa 674

Jump to navigation
Jump to search

## Contents

## 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