I have this programming prompt where I have been asked to find the number of permutations of a 32 coin toss sequence that do not have three consecutive heads in a row.
I have been tasked to find this with dynamic programming and I am having a hell of a time trying to figure out the recursive algorithm.
I have tried a two variable approach where I try and keep track of whether the previous two flips were heads or tails and then incrementing based upon that. I have also tried breaking it into sub-problems where I start with a singular toss and then work my way up the full 32 tosses.
And I'm having a hard time visualizing how to approach this and figuring out how to keep track of everything as the algorithm commences.
Any help would be greatly appreciated.