Nsryjdtyk

Suppose we have a boolean array of length X. The only rule is, TRUE must not occur twice in adjacent places. Especially the array with only false values is allowed. E.g. this is forbidden: [1,1,0,0,0] and these is allowed: [1,0,0,0,0], [0,0,0,0,0], [1,0,1,0,1] etc. How can I use dynamic programming to determine how many different valid arrays of length X there are?

Let T_i be the number of arrays of length i that meet your criterion and end in 1, and let F_i be the number of arrays of length i that meet your criterion and do not end in 1.

Then:

• 
  T₀ = 0


• 
  F₀ = 1


• 
  T_i+1 = F_i. (Each array of length i+1 that meets your criterion and ends in 1 consists of an array of length i that meets your criterion and does not end in 1, plus an extra 1 at the end.)


• 
  F_i+1 = F_i + T_i. (Each array of length i+1 that meets your criterion and does not end in 1 consists of an array of length i that meets your criterion, plus an extra 0 at the end.)


• You want F_X + T_X.

So you can just write a loop that calculates F_i and T_i for each i from 0 to X, and then return F_X + T_X.

(This isn't even dynamic programming, per se, because you don't need to store partial values; F_i+1 and T_i+1 depend only on F_i and T_i. So this is O(X) time and O(1) space.)

I think you can calculate the number without using DP. Since you know the total number of arrays for length N, that is `2^N'.

Now you need to deduct those bad arrays that do not qualify if they have adjacent 1's. For an array of length N, there are these cases

1. the array has no 1's, only one case, and it is a valid array

2. the array has one 1's, all cases are valid

3. the array has two 1's, there are N - 1 cases which are not valid

4. the array has three 1's, there are (N-1) * (N-2) / 2 cases which are not valid

...

The dp solution would have two state parameters. One is the position of the array and the other is the previous position’s value. If the previous position’s value is 1 then you can only choose 0. If the previous position’s value is 0 then you can choose either 1 or 0. Hope this helps.

You don't really need dynamic programming.
For array length X the number of valid arrays is Fib(X+1), where Fib is the array of fibonacci numbers.

X=1: valid arrays: 2

X=2: valid arrays: 3

X=3: valid arrays: 5

X=4: valid arrays: 8

and so on...

Demonstration:

Let's assume we are looking for the arrays for X and we know the number of valid arrays for X-1. We can freely add a zero to the end of each of these X-1 length arrays, so that's F(X-1) so far. We can also add a '1' to the end of each X-1 arrays which ends with 0. But how many of those arrays are? Well, it's exactly F(X-2) because we could generate the zero ending X-1 length arrays exactly the same way: by adding a zero at the end of each X-2 length arrays. So F(X) = F(X-1) + F(X-2)
And that's exactly the definition of the Fibonacci array.

All we have to do is manually calculate the first two element to determinate if it's exactly the Fibonacci array or is it shifted.

You can even find a formula to calculate the Nth element of the fibonacci array, so it can be solved in O(1).