Count how many arrays of a specific type exist - O(N) Dynamic Programming

Question

Consider an array of N + 2 binary digits (1 and 0), which contains at least one '1' and three '0'. The last and first digit of the array is 0.

Given two numbers, let's say p and q, determine how many different arrays exist which respect what I've said right above and have all the CONTINUOUS sequences of '1' minimum p and maximum q in length.

This can be solved in O(N) with DP. But how? I just need the recurrence relation explained. Can you help me?

Thank you very much!

LE (example)

N = 5

p = 2, q = 3

The result is 8 and these are the possibilities:

0000110

0001100

0001110

0011000

0011100

0110000

0110110

0111000

Answer 1

Hints:

1. first and last $0$ could always be omitted from discussion
2. each array ends with either $0$ or $1$
   • So: $f(n) = f(n,0) + f(n,1)$
3. if it ends with $0$, we don't care what is the second last bit
   • So: $f(n,0) = ? + ?$
4. if it ends with $1$, than it must be $i$ $1$'s with a preceding $0$, where $p \le i \le q$
   • So: $f(n,1) = ? + ? + ? + ... + ?$

The run time is $O((q-p)N) = O(N)$ for fixed $p$ and $q$.