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