You're right. I hadn't quite thought it through, but it would work well: eg. for 8 coin values, if you need to calculate the number of ways to make 2.00, you need to make at most 200*8=1600 calls to the recursive function. So you get O(n) efficiency. But it still seems like you should be able to do better: O(1) would be possible with a closed-form formula. edit: Oh, I noticed you actually implemented it with memoization. Great!
That's way beyond my maths ability. Do you think you could find such a formula? I know there's Binet's formula for Fibonacci, but it's impractical for larger numbers as the floating point errors start to affec tthe results (on most machines anyway.) O(1) would be possible with a closed-form formula.
Yeah, it's tough, I don't really know how to go about it. But here's at least a demonstration for three denominations, {1, 2, 5}: (n is the total amount to add up to) numfives = math.floor(n/5.)+1 return int( numfives * (n % 5 + n + 3)/4 - (numfives % 2) * (n % 2 - 0.5) / 2. ) Disgusting, I know! But it works: I double checked it against your code, it gives the same result up to n=5000. An estimate for four denominations {1, 2, 5, 10} is n^3/600; for five denominations {1, 2, 5, 10, 25}, n^4/60000. I got these by summing crudely and dropping low order terms. They seem to be asymptotic: the estimate for five denominations is accurate to within 5% of the true value for n > 2000. That might seem silly but count_change does get quite slow for n >> 10^6 (that's $10,000.00), while the approximation is good to within 0.01%. edit: You could write a program that returns an estimator function for a given set of denominations. See Faulhaber's formula. def onetwofive(n):
I'm impressed you managed a solution for 3 coins. > count_change does get quite slow for n >> 10^6 (that's $10,000.00) From a pure math angle, both memo & dynamic programming versions are linear in time and space. As you said though, those numbers are growing exponentially meaning the space will grow exponentially too.