The obvious answer is to memoize count-change. A similar approach is to use dynamic programming. In python: def count_change(change): return count(change, len(coin_value)) def count(change, num_coins): result=[[0 for j in range(num_coins)] for i in range(change + 1)] for i in range(change + 1): for j in range(num_coins): if i == 0: # exact change IS possible with given coin_value result[i][j] = 1 elif j == 0: # no coins left, still change to give result[i][j] = 0 elif coin_value[j] > i: # current coin is too large result[i][j] = result[i][j-1] else: # tally how many ways we can get here from previous results result[i][j] = result[i-coin_value[j]][j] + result[i][j-1] return result[change][num_coins-1] >>> count_change(100) 292 coin_value = [0, 1, 5, 10, 25, 50] >>> from count_change import count_change
Nice. Python is such an elegant language. I can't follow your logic immediately (I'll come back to it later when I have time), but looks like it's getting the right result. Is it fast?
About the speed: I added a counter to check how many times it went through the inner loop: count_change(100) = 292: with 606 steps count_change(200) = 2435: with 1206 steps count_change(300) = 9590: with 1806 steps ... count_change(1000) = 801451: with 6006 steps You can see it's going up linearly That's the dynamic programming approach. A similar technique is memoization which lends itself very nicely to the way the original problem is given in scheme. I'll use racket: Adding a count to the program given in SICP (define steps 0) (define (count-change amount) (cc amount 5)) (define (cc amount kinds-of-coins) (set! steps (add1 steps)) (cond ((= amount 0) 1) ((or (< amount 0) (= kinds-of-coins 0)) 0) (else (+ (cc amount (- kinds-of-coins 1)) (cc (- amount (first-denomination kinds-of-coins)) kinds-of-coins))))) (define (first-denomination kinds-of-coins) (cond ((= kinds-of-coins 1) 1) ((= kinds-of-coins 2) 5) ((= kinds-of-coins 3) 10) ((= kinds-of-coins 4) 25) ((= kinds-of-coins 5) 50))) (count-change 100): 292 in 15499 steps (count-change 200): 2435 in 229589 steps (count-change 300): 9590 in 1292591 steps Yeah - I'm not even going to try (count-change 1000) This is the problem with tree recursion :( Converting to a memoized version (I'm cheating by using a library that gives define/memo but it's evasy enough to write a memoized version of a function. (define (count-change amount) (cc/memo amount 5)) (set! steps (add1 steps)) (cond ((= amount 0) 1) ((or (< amount 0) (= kinds-of-coins 0)) 0) (else (+ (cc/memo amount (- kinds-of-coins 1)) (cc/memo (- amount (first-denomination kinds-of-coins)) kinds-of-coins))))) (count-change 100): 292 in 250 steps (count-change 200): 2435 in 496 steps (count-change 300): 9590 in 742 steps (count-change 1000): 801451 in 2464 steps That's even less steps than using dynamic programming although it probably uses a little extra memory to store teh memoized values. #lang racket (require memoize) (define/memo (cc/memo amount kinds-of-coins)
It's an O(n) algorithm - although there is an inner loop - since the number of coin values is fixed it's still a linear algorithm So it's a very fast algorithm. The basic approach with dynamic programming is: Start from the bottom and save the base case results. Go to the "nest level" and calculate those results based on the previously stored results. Keep going until you get your answer. The i - loop represents the amount of change to be given The j - loop represents how many distinct coin values there are. Note that isn't the number of coins in change given its how many coin values you have. The insight is that to calculate how many ways to give change for a given amount using coins of specific values: a) Use 1 of your coins and deduct that from the amount. Result for a) is 1 + ways to count (amount - coin used). e.g. for 57¢ - you can use 1¢ and calculate 56¢. Those results are stored in the results[i] - since python doesn't have native arrays result is a list of lists b) Result for b) is how many ways can you give change by ignoring all coins of one specific value. e.g. for 57¢ - how many ways can you give change when you NEVER use any 1¢ coins? Those results are stored in the result[amount] list indexed by how many coin values are used For a given amount and given number of coin values total = a) + b) To find how many ways to count 10¢ using 1¢, 5¢, 10¢, 25¢, 50¢ Build up the result 'array' like this How many ways to give 0¢ change result[0] = [1, 1, 1, 1, 1, 1] - there is 1 way of giving 0¢ change with a 0¢ coin there is 1 way of giving 0¢ change with 0¢ and 1¢ coins. there is 1 way of giving 0¢ change with 0¢, 1¢, 5¢ coins... How many ways to give 1¢ change result[1] = [0, 1, 1, 1, 1, 1] - there is no way of giving 1¢ change with a 0¢ coin there is 1 way of giving 1¢ change with with 0¢ and 1¢ coins there is 1 way of giving 1¢ change with with 0¢, 1¢, 5¢ coins... these don't change until we hit 5¢ result[5] = [0, 1, 2, 2, 2, 2] - there is no way of giving 5¢ change with a 0¢ coin there is 1 way of giving 5¢ change with with 0¢ and 1¢ coins there are 2 ways of giving 5¢ change with with 0¢, 1¢, 5¢ coins... these don't change until we get to 10¢ result[10] = [0, 1, 3, 4, 4, 4] - there is no way of giving 10¢ change with a 0¢ coin there is 1 way of giving 10¢ change with with 0¢ and 1¢ coins result there are 3 ways of giving 10¢ change with with 0¢, 1¢, 5¢ coins there are 4 ways of giving 10¢ change with with 0¢, 1¢, 5¢, 10¢ coins there are 4 ways of giving 10¢ change with with 0¢, 1¢, 5¢, 10¢, 25¢ coins there are 4 ways of giving 10¢ change with with 0¢, 1¢, 5¢, 10¢, 25¢, 50¢ coins. Since we want to know how many ways using all coins - the answer is at the last value in the last row which is 4.