Problem · Hard · 35 min
Postage with stamps
- Hard
- Dynamic programming
A post office sells stamps of several values. You can use as many stamps of each value as you want. You must pay the postage exactly.
Write countWays(amount, stamps). It returns the number of different ways to make amount with the stamp values in stamps.
- Ways that use the same stamps in a different order count as one way.
1 + 2and2 + 1are the same way. amountis a whole number that is 0 or more. For anamountof 0, there is one way: use no stamps.- Every stamp value is a whole number that is at least 1. The values in
stampsare all different. The list can be empty. - If there is no way, return 0.
Examples
| Call | Result |
|---|---|
countWays(5, [1, 2, 5]) |
4 |
countWays(3, [2]) |
0 |
countWays(0, [1, 2]) |
1 |
Tasks
2 to do
Task 1, not checked yet. Make
countWayspass the example tests.Task 2, not checked yet. Make
countWayspass the hidden tests.
Task 1 of 2
Make countWays pass the example tests.