Dynamic Programming for test tube

Question

Eli is a teenager who loves to study chemistry. She recently joined a chemistry research lab.

Dr. Phil wants her to just play around with some chemicals and observe their reaction.

Therefore, he gave her a one-row tray of test tubes with the different chemical inside of them and told her:

"Mix these chemical together anyhow that you like, but the you have to follow two rules:

1. Never make a mixture that has two chemicals that their tubes are next to each other.

2. Keep adding more chemical to the mixture until it is not violating the new rule."

For example, in the image you can see she was given 5 tubes and she is able to make 4 different mixture without violating the rule: {1,3,5}, {2,4}, {2,5}, {1,4}.

But she cannot mix 1 and 3 only because she still can add 5 without violating the rules.

She is curious to know how many different mixtures she can make without violating the rule with any given number of tubes.

That's why she asks you write a code to calculate it for her.

Input

The input will consist of a sequence of numbers N, 1 ≤ N ≤ 76. Each number will be on a separate line.

The input will be terminated by 0.

Output

Output the number of different mixture she can make without violating the rule mentioned above on a single line as show in the sample. The number of all subsets will be less than 2^31

Input:

1
2
3
4
5
6
7
8

Output:

0
0
1
3
4
5
7
9

Is it possible for me to use the formula like Mix[i] = Mix[i - 2] + Mix[i - 3] to find the answer, because I notice a pattern, so I tried using this formula, but can't quite the answer for input 4,5 and 6

Answer 1

You're quite close to the answer. Let's define an array called dp where dp[i] is the number of ways to mix i chemicals always including the ith chemical in the mixure. To compute dp[i], we have two cases:

1. Include the i - 2th chemical, with dp[i - 2] possible ways.
2. Include the i - 3th chemical but not the i - 2th chemical, with dp[i - 3] possible ways.

We must either include the i - 2th chemical or the i - 3th chemical because if we don't include one of them, it would be possible to include the i - 2th chemical which violates the rule.

So dp[i] = dp[i - 2] + dp[i - 3], which matches your formula. However, this is not the solution (yet). Remember that dp[i] only counts the number of possible mixtures including the ith chemical. We need to add to that the number of possible mixtures not including the ith chemical, which is simply dp[i - 1]. Therefore, our answer is dp[i] + dp[i - 1].

For some implementation details, we have to hardcode dp[0], dp[1], and dp[2] as our base cases. Also, we need to hardcode the output for inputs 1 to 3 because for those inputs it's possible to have a "mixture" consisting of a single chemical which isn't valid.