CODEWITHSUNDEEP
algorithmcombinatorics
hearuige
hearuige

Reputation: 11

Determine how many different arrays are possible

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?

Upvotes: 1

Views: 87

Answers (4)

Selindek
Selindek

Reputation: 3423

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).

Upvotes: 0

Md Golam Rahman Tushar
Md Golam Rahman Tushar

Reputation: 2375

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.

Upvotes: 0

ruakh
ruakh

Reputation: 183301

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

Then:

  • T0 = 0
  • F0 = 1
  • Ti+1 = Fi. (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.)
  • Fi+1 = Fi + Ti. (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 FX + TX.

So you can just write a loop that calculates Fi and Ti for each i from 0 to X, and then return FX + TX.

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

Upvotes: 3

CS Pei
CS Pei

Reputation: 11047

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

...

Upvotes: 0

Related Questions