试管动态规划

Question

Eli 是一个热爱化学的少年。她最近加入了一个化学研究实验室。

博士。 Phil 希望她只是玩弄一些化学品并观察它们的反应。

因此，他给了她一排试管托盘，里面装有不同的化学物质 并告诉她：

“随意混合这些化学物质，但你必须遵守两条规则：

1. 切勿混合含有两种管子彼此相邻的化学品。

2. 继续向混合物中添加更多化学品，直到它不违反新规则。"

例如，在图片中您可以看到她得到了 5 支试管，并且她能够在不违反规则的情况下制作 4 种不同的混合物：{1,3,5}、{2,4}、{2、 5}, {1,4}.

但她不能混合 1 和 3 只是因为她仍然可以 不违反规则加5。

她很想知道有多少种不同的混合物 她可以在不违反任何规则的情况下 给定的管数。

这就是她问你的原因 写个代码帮她计算一下。

输入

输入将由数字序列 N 组成，1 ≤ N ≤ 76。每个数字都在 单独的行。

输入将以0结束。

输出

输出她在不违反上述规则的情况下可以制作的不同混合物的数量 如示例所示，在单行上方。所有子集的数量将小于 2^31

输入：

1
2
3
4
5
6
7
8

输出：

0
0
1
3
4
5
7
9

我是否可以使用像 Mix[i] = Mix[i - 2] + Mix[i - 3] 这样的公式来找到答案，因为我注意到一个模式，所以我尝试使用这个公式, 但不能完全回答输入 4,5 和 6

Answer 1

你已经很接近答案了。让我们定义一个名为 dp 的数组，其中 dp[i] 是混合 i 化学品的方式的数量 总是包括混合物中的第 i 化学品.要计算 dp[i]，我们有两种情况：

1. 包括第 i - 2 种化学品，有 dp[i - 2] 种可能的方式。
2. 包括第 i - 3 种化学物质但不包括第 i - 2 种化学物质，有 dp[i - 3] 种可能的方式。

我们必须包括第 i - 2 种化学品或第 i - 3 种化学品，因为如果我们不包括其中之一，则有可能包括第 i - 2 种违反规则的化学品。

所以 dp[i] = dp[i - 2] + dp[i - 3]，与您的公式相符。然而，这不是解决方案（还）。请记住，dp[i] 仅计算包括第 i 种化学物质在内的可能混合物的数量。我们还需要添加不包括第 i 种化学物质的可能混合物的数量，即 dp[i - 1]。因此，我们的答案是dp[i] + dp[i - 1].

对于一些实现细节，我们必须硬编码 dp[0]、dp[1] 和 dp[2] 作为我们的基本情况。此外，我们需要对输入 1 到 3 的输出进行硬编码，因为对于这些输入，可能 "mixture" 由一种无效的化学物质组成。