"""
 coinsums.py

 https://projecteuler.net/problem=31

 Define ways(target, i)
   to be the number of ways to get to target sum
   using coins[0,1,2,...i]

 The nswer we want is ways(200, 7).

 The recursion relation is :
 
   ways(target, i) recursion relation : 
                  ways(target, 0) = 1
                  ways(target, i) = sum over k of ways(new_target, i-1)
                                    where new_target = target - k * coins[i];
                                    and new_target > 0, k=0,1,2,3,...

 We've encoded this below using a top-down explicit recursive approach,
 with memoization to avoid repeatededly computing the same result.

 $ python coinsums.py
 The answer is  73682  

 ... which agrees with the project euler answer


Jim Mahoney | cs.marlbobor.college | April 2019 | MIT License
"""

# coin denominations
#   index     0  1  2   3   4   5    6    7 
coins =      [1, 2, 5, 10, 20, 50, 100, 200]

cache = {}  # memoization for ways()

def ways(target, i):
    """ Return number of ways to do the coinsum ... see above """
    if not (target, i) in cache:
        cache[(target, i)] = _ways(target, i)
    return cache[(target, i)]

def _ways(target, i):
    """ non-cached helper for ways() """
    if i == 0:
        return 1
    else:
        result = 0
        k = 0
        while True:
            new_target = target - k * coins[i]
            if new_target < 0:
                return result
            result = result + ways(new_target, i - 1)
            k = k + 1

print("The answer is ", ways(200, 7))