Solution for Sedgewick Analytic Combinatorics homework 1 http://ac.cs.princeton.edu/lectures/AC01-OGFs.pdf

change.rb

#Solution for Sedgewick Analytic Combinatorics homework 1
#http://ac.cs.princeton.edu/lectures/AC01-OGFs.pdf
#Chad Brewbaker
#crb002@gmail.com    | Software Engineer @ Telligen
#January 30, 2013

best =0
coins=*(1..100)
coins.combination(4).each{ |currency|    		
						memo = [0]*100
						(0..99).each{ |i|
							currency.each{ |c|	
								if((i+1)== c)
									memo[i] = memo[i]+1
								else
									if((i+1-c) > 0  )
										memo[i] = memo[i]+memo[(i-c)]
									end
								end	
							}		
						}
						if (memo[-1] >= best)
							print [currency,memo].inspect + "\n"
							best = memo[-1]
						end
					}
# Answer is coin values [1,2,3,4] which produces the Fibbonacci numbers http://oeis.org/A000045