[Haskell-cafe] Re: Coin changing algorithm
Okasaki, C. DR EECS
Christopher.Okasaki at usma.edu
Thu Jul 14 22:25:19 EDT 2005
> During a single evaluation the recursive calls never "collide", so
> unless this overlap is optimized, then the subproblem memoizing won't do
Actually, the recursive calls can collide. For example, if you are trying to make 87 cents with 7 coins, you can make the first 80 cents with four coins using either 50-10-10-10 or 20-20-20-20. Either way, you'll end up making a recursive call on 7 cents and 3 coins. Admittedly, however, with this choice of coin denominations, you don't get very many such collisions...
More information about the Haskell-Cafe