[hadoop@iZ25s7cmfyrZ test]$ cat coin_dp.py

#!/usr/bin/env python

#n=11

n=input("n=") n_coin_dict={} coin_list=(1,3,5) for n_i in range(n+1):     #print n_i     for j in range(len(coin_list)):         c_j=coin_list[j]         if n_i==0:             n_coin_dict[(n_i, c_j)]=0         else:             if n_i < c_j:                 n_coin_dict[(n_i, c_j)]=n_coin_dict[(n_i,coin_list[j-1])]             else:                 n_coin_dict[(n_i, c_j)]=n_coin_dict[(n_i-c_j,c_j)]+1 

print n, coin_list, n_coin_dict[(n,max(coin_list))]