[Haskell-cafe] Re: Coin changing algorithm

Okasaki, C. DR EECS Christopher.Okasaki at usma.edu
Thu Jul 14 22:25:19 EDT 2005

ChrisK wrote:
> During a single evaluation the recursive calls never "collide", so
> unless this overlap is optimized, then the subproblem memoizing won't do
> anything...

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...
-- Chris

More information about the Haskell-Cafe mailing list