I'm taking my first steps into recursion and dynamic programming and have a question about forming subproblems to model the recursion.
Problem:
How many different ways are there to flip a fair coin 5 times and not have three or more heads in a row?
If some could put up some heavily commented code (Ruby preferred but not essential) to help me get there. I am not a student if that matters, this is a modification of a Project Euler problem to make it very simple for me to grasp. I just need to get the hang of writing recursion formulas.
If you would like to abstract the problem into how many different ways are there to flip a fair coin Y times and not have Z or more heads in a row, that may be beneficial as well. Thanks again, this website rocks.