"""
Project Euler Problem 31
========================

In England the currency is made up of pound, -L-, and pence, p, and there
are eight coins in general circulation:

  1p, 2p, 5p, 10p, 20p, 50p, -L-1 (100p) and -L-2 (200p).

It is possible to make -L-2 in the following way:

  1 * -L-1 + 1 * 50p + 2 * 20p + 1 * 5p + 1 * 2p + 3 * 1p

How many different ways can -L-2 be made using any number of coins?
"""


denominations = [1,2,5,10,20,50,100,200]

no_ways_list = [[1 for i in range(0,201)]]
no_ways_list[0][0] = 0


for i in range(1,len(denominations)):
  coin = denominations[i]
  no_ways = [0]
  for value in range(1, 201):
    ways = no_ways_list[i-1][value]
    index  = 1
    curr_value = coin * index
    while curr_value <= value:
      if curr_value == value:
        ways += 1
      else:
        ways = ways + no_ways_list[i-1][value - curr_value]
      index += 1
      curr_value = coin * index
    no_ways.append(ways)
  no_ways_list.append(no_ways)

print no_ways_list[-1][-1]

c68de4cff307f8d23752d22f63afbc4a65f99b6e
"""
Project Euler Problem 31
========================

In England the currency is made up of pound, -L-, and pence, p, and there
are eight coins in general circulation:

  1p, 2p, 5p, 10p, 20p, 50p, -L-1 (100p) and -L-2 (200p).

It is possible to make -L-2 in the following way:

  1 * -L-1 + 1 * 50p + 2 * 20p + 1 * 5p + 1 * 2p + 3 * 1p

How many different ways can -L-2 be made using any number of coins?
"""


denominations = [1,2,5,10,20,50,100,200]

no_ways_list = [[1 for i in range(0,201)]]
no_ways_list[0][0] = 0


for i in range(1,len(denominations)):
  coin = denominations[i]
  no_ways = [0]
  for value in range(1, 201):
    ways = no_ways_list[i-1][value]
    index  = 1
    curr_value = coin * index
    while curr_value <= value:
      if curr_value == value:
        ways += 1
      else:
        ways = ways + no_ways_list[i-1][value - curr_value]
      index += 1
      curr_value = coin * index
    no_ways.append(ways)
  no_ways_list.append(no_ways)

print no_ways_list[-1][-1]
