Dynamic Programming Recursive Algorithm - Series of coin tosses 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.
Let $x(n)$ be the number of $n$-terms sequences of heads and tails, avoiding three consecutive heads.

The goal is to compute $x(32)$ via dynamic programming.

I'll do it in two different ways . . .

Method $(1)$:$\;1$-variable recursion.

By direct calculation,
$$x(0)=1,\;\;x(1)=2,\;\;x(2)=4$$
and for $n \ge 3$, we get
$$x(n)=x(n-1)+x(n-2)+x(n-3)$$
Explanation:

Call a sequence of heads and tails "qualifying" if it avoids three consecutive heads.

Assuming $n \ge 3$, an $n$-term sequence of heads and tails is qualifying if and only if it has one of the forms
\begin{align*}
&amp;Ts'\\[4pt]
&amp;HTs''\\[4pt]
&amp;HHTs'''\\[4pt]
\end{align*}
where $s',s'',s'''$ are qualifying sequences of lengths $n-1,n-2,n-3$, respectively.

Based on the above recursion, we get the following dynamic program, expressed as pseudocode . . .

function x(n):
    if n \le 2, return 2^n
    a,b,c= 1,2,4
    i = 0
    loop begin
        d=a+b+c
        i = i + 1
        if i = n then break
        a,b,c=b,c,d 
    loop end
    return d
end function


Method $(2)$:$\;2$-variable recursion.

We have $x(n) = f(0,n)$, where $f(h,n)$ is the number of qualifying $n$-term sequences, assuming $h$ consecutive heads are already in progress.

Then $f(h,n)$ satisfies the recursion
\begin{align*}
&amp;\text{if}\;h \ge 3,\;\text{then}\\[4pt]
&amp;\;\;\;\;f(h,n) = 0\\[4pt]
&amp;\text{else if}\;n = 0,\;\text{then}\\[4pt]
&amp;\;\;\;\;f(h,n) = 1\\[4pt]
&amp;\text{else}\\[4pt]
&amp;\;\;\;\;f(h,n) = f(0,n-1)+f(h+1,n-1)\\[4pt]
&amp;\text{end if}\\[4pt]
\end{align*}
Explanation:


If there are $3$ consecutive heads in progress, there are no qualifying sequences.$\\[4pt]$
Else if there are no tosses remaining, the empty sequence qualifies.$\\[4pt]$
Else a tail resets $h$ to zero, a head increases $h$ by $1$, and either way, $n$ decreases by $1$.$\\[4pt]$


Based on the above recursion, we get the following dynamic program, expressed as pseudocode . . .

function x(n):
    if n = 0, return 1
    a0,a1,a2 = 1,1,1
    i = 0
    loop begin
        b0 = a0 + a1
        b1 = a0 + a2
        b2 = a0
        i = i + 1
        if i = n then break
        a0,a1,a2 = b0,b1,b2 
    loop end
    return b0
end function


With either of the two methods, we get $x(32) = 334745777$.
I asked my calculus professor this questions and he said it can be solved using a geometric series.  So in a handful of lines of code.  The answer he gave me was still roughly 4.1 billion possibilities where you do not have heads 3 times.  The series simplified to this:
2^32 - 2^28 + 1
Any thoughts?