a thoughtful web.
Good ideas and conversation. No ads, no tracking.   Login or Take a Tour!
comment
yakov  ·  3360 days ago  ·  link  ·    ·  parent  ·  post: A nice problem from SICP

You're right. I hadn't quite thought it through, but it would work well: eg. for 8 coin values, if you need to calculate the number of ways to make 2.00, you need to make at most 200*8=1600 calls to the recursive function. So you get O(n) efficiency.

But it still seems like you should be able to do better: O(1) would be possible with a closed-form formula.

edit: Oh, I noticed you actually implemented it with memoization. Great!