Skip to content

Instantly share code, notes, and snippets.

@zhangys-lucky

zhangys-lucky/project_euler_31_coin_sum.py

Created August 19, 2015 00:48
Show Gist options
  • Save zhangys-lucky/20bc22d871a83ab81556 to your computer and use it in GitHub Desktop.
Save zhangys-lucky/20bc22d871a83ab81556 to your computer and use it in GitHub Desktop.
Download ZIP
project_euler_31_coin_sum using dynamic programming
Raw
project_euler_31_coin_sum.py
#! /usr/bin/python
MAX_COIN = 200
arr = [i * 0 for i in range(201)]
arr[0] = 1
for coin in [1,2,5,10,20,50,100,200]:
j = coin
while j <= MAX_COIN:
arr[j] += arr[j - coin]
j += 1
print(arr)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment