Coin Toss in Dynamic Programming

Revision en1, by jhjfbsbfkbjfnfnfjfj, 2020-03-31 18:18:56

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.

Tags #dp, #dynamic programing, #maketouristgreatagain

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English jhjfbsbfkbjfnfnfjfj 2020-03-31 18:18:56 810 Initial revision (published)