Challenge: Number of Ways to Represent N Dollars
In this lesson you will write an algorithm to solve a famous dynamic programming problem, finding the number of ways to represent an amount using bills and coins.
We'll cover the following
Problem statement
Given a list of currency bills, you are required to count the number of ways in which you can represent a certain amount. For example, if you have only two kinds of bills, $10 and $20, and you want to represent $30, there are only two ways:
- 3 bills of $10
- 1 bill of $20 and 1 bill of $10.
Input
You will get a list of currency bills
and the amount
you are required to make as input. You have to count the number of ways the amount
can be made using the currency bills provided in the bills
list.
bills = [10, 20]
amount = 30
Output
Your program should return the count of the number of ways amount
can be represented using dollar bills given to you in the list bills
.
countways([10, 20], 30) = 2
Coding challenge
As you design the algorithm take special care that you do not overcount. $30 can be represented with $20+$10 as well as $10+$20, but these are the same thing. Therefore, you should not count both cases.
A simple recursive solution will timeout for large inputs, thus, you should try to write a dynamic programming algorithm. Start with a recursive solution and build up to a dynamic solution. Your solution may use a top-down or bottom-up approach. Set stressTesting
to False
to test your simple recursive solution.
Get hands-on with 1200+ tech skills courses.