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.

First, I wrote this recursive algorithm, but I wasn't sure it would give the correct answer. I only checked where N was 1, 2, 3, 4, 5, 6, and the algorithm found them correct.

After that, I found this Dynamic Programming solution. I think this algorithm finds the answers correct.

When N was 32, both algorithms found 334745777.

I hope it will help.

thanks a lot. what is pre1 and pre2 and also can you tell about what states you considered in dp and how you deduced it?

Pre1 is the coin we selected from previous recursion and pre2 is the coin we selected from the previous recursion of the previous recursion.

First of all, I created a tree. When I examined the tree after creating it, I decided that the number of leaves for each N height is the sum of the number of leaves for the heights of N-1, N-2, and N-3.

For example, if the problem was finding the number of permutations of a 32 coin toss sequence that do not has four consecutive heads in a row, this would be the code we had to write:

Or we can write like this so that there will be less addition: