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.