Ways to pay

You have as many coins as you like of each value in coins (all different, all at least 1). Return the number of different ways to pay exactly amount. Only how many coins of each value you use matters, not their order: 1 + 2 and 2 + 1 are the same way.

ways_to_pay(5, [1, 2, 5])     # 4
# 5, 2+2+1, 2+1+1+1, 1+1+1+1+1
ways_to_pay(4, [1, 2, 3])     # 4, not 7
ways_to_pay(0, [7])           # 1: pay with nothing

Limits

• amount is up to 100,000 and there are up to 30 coin values. The counts can be very large; Python’s whole numbers hold them exactly.
• Python stops at about 1,000 nested calls, and a function wrapped in functools.cache stops after a few hundred in the browser. The big tests need far more than that, so memoised recursion fails them. Fill a table with a loop (lesson 3).