Note that the memory requirements in the Coin Change solution is O(N), and that is not optimal. You should be able to get away with O(max(denom) - min(denom)) (

Note that the memory requirements in the Coin Change solution is O(N), and that is not optimal. You should be able to get away with O(max(denom) - min(denom)) (you don't need to cache everything).