So I have this programming prompt which asks me to figure out how many permutations of a 32 coin toss sequence do not have three or more heads consecutively tossed. We are supposed to use Dynamic Programming to do this and I'm having a hell of a time identifying the recursive algorithm for this.
My first thought was a bottom up approach where I start from a singular toss and then increment a variable whenever I find a sequence that has three heads in a row and then subtract that number from the total number of possible permutations to get the answer but I'm having trouble implementing the logic behind that.
I see that instead of thinking increasingly large sequences, it would be better to think of each individual toss in the sequence. Mostly what I'm having trouble with is how I should be keeping track of all this.
For example, the first toss is a H, that affects the rest of the sequence because I can't have 2 more H's consecutively, but if the first toss is a T, that doesn't affect the rest of the sequence. So, do I wait till the third toss to tell if I increment? Do I discard the first toss if it's a T? I'm having quite a bit of trouble visualizing and comprehending this problem.