你有一些乐高塑料砖，所有砖都是1x1x1。你还有一块瓷砖，1xN（N <= 80），你应放置乐高积木。您可以按顺序对它们进行排序（如果一个序列具有3个或更多个连续的砖块，则一个序列是正确的），并且您必须在2个序列之间至少有1个空白空间。您应该计算可以将砖块放在瓷砖上的不同组合的数量。
这是一个例子：
如果图块是1x7，则有17种不同的组合。
输入：7输出：17
pic of the example http://mendo.mk/task_files/kocki.gif
此外，如果你没有砖，它被算作1组合。
我已经解决了这个问题，我找到了计算瓷砖最大长度为14（3个序列）的可能组合的方法。我发现它使用for循环。
我最大的问题是需要运行的大量for循环。例如，对于1个序列，我使用1个循环，2个序列2个循环+ 1个1个序列...所以如果我使用所有80个砖，我可以创建20个序列，我将不得不使用超过210个循环，这是数量巨大。所以，如果我可以将它们嵌套在一个中，那将是很好的。我尝试了它，它变得混乱，它没有给出正确的答案。
新代码：
#include <iostream>
using namespace std;
int main()
{
long long int places, combinations = 1;
cin >> places;
long long int f[80], g[80];
f[0] = 0;
f[1] = 0;
f[2] = 0;
g[0] = 1;
g[1] = 1;
g[2] = 1;
for(int i = 3; i<=places; i++)
{
f[i] = f[i-1] + g[i-3];
g[i] = f[i-1] + g[i-1];
}
combinations = f[places] + g[places];
cout << combinations;
return 0;
}
如果这是一个计数问题（不输出组合，而只是计算它们），这很容易。假设我们现在解决了n≥3来解决它为n + 1，我们通过归纳解决它：
假设f是一个函数，它显示了最后一个项目是砖的可能方式的数量。类似地，g是一个函数，它显示了最后一个项目不是砖的可能方式的数量。让我们定义h = f+g，它是所有可能方式的数量。
所以我们有：
f(n+1) = f(n) + g(n-2)
g(n+1) = g(n) + f(n)
初始条件：
for n=0,1,2: g=1, f= 0.
for n = 3: g=1,f=1
样品：
n=4: g=2,f=2 ==> h=4
n=5: g=4, f= 3 ==> h=7
n=6: g=7, f= 4 ==> h=11
n=7: g=11,f=6 ==> h=17
我们可以在O(n)中使用一个for循环来解决它。
f(n+1) = f(n) + g(n-2)
g(n+1) = g(n) + f(n)
首先，让我们证明第一部分：
请记住，我们假设f（n）是一个工作解决方案，在最后一项中有一个塑料砖，而g（n）是一个在最后一项中没有砖的工作解决方案。
f（n + 1）可以通过在最后位置添加一个砖从f（n）获得。通过在g（n-2）之后添加三个砖也可以获得f（n + 1），它意味着n-1，n，n + 1的单元。
请注意，我们不能在g（n-1）或g（n）之后添加砖来为f（n + 1）创建有效的解决方案，因为它们不是有效的解决方案（连续砖的数量小于3）。另外，请注意，我们不需要计算g（n-3）之后添加砖块所产生的方式的数量，因为它们之前是由f（n）枚举的。所以我们有f(n+1) = f(n) + g(n-2)。
以同样的方式，我们可以证明g(n+1) = f(n)+g(n)这种情况更容易，因为g（n + 1）可以简单地从任何有效的解决方案到n，因为这里没有3个连续砖块障碍，它们可以在任何有效的解决方案之后。
作为一个有数学训练的人，而不是CS，我觉得有必要提一下，虽然Saeed Amiri的算法非常好，并且可能足够快地为N达到几百万（当然有恒定的记忆），有一个从时间角度看更好的算法。
我会去他离开的地方：
f(n+1) = f(n) + g(n-2)
g(n+1) = f(n) + g(n)
由于f和g是离散函数，因此可以将它们视为序列。这就成了递归关系的线性系统。幸运的是，这样的系统可以完全解决，因此可以呈现f和g的显式形式。 不幸的是，SO似乎不像Math.SE那样支持MathJax，所以我为这里的低质量方程式道歉。 让
| f(n) |
|f(n-1)|
u(n)=|f(n-2)|
| g(n) |
|g(n-1)|
|g(n-2)|
也就是说，u（n）是向量行。然后，以下是真的：
|f(n+1)| |1 0 0 0 0 1| | f(n) | | f(n) | |1 0 0 0 0 0| |f(n-1)| |f(n-1)| = |0 1 0 0 0 0| . |f(n-2)| |g(n+1)| |1 0 0 1 0 0| | g(n) | | g(n) | |0 0 0 1 0 0| |g(n-1)| |g(n-1)| |0 0 0 0 1 0| |g(n-2)|
接下来是u(n) = A * u(n-1)，其中A是上面的矩阵。
然后，u(n) = (A^(n-2)) * u(2)，其中u(2)是向量，包含问题的初始值。反过来，这给出了一个O(log(n))复杂度的算法，因为你可以使用快速取幂来计算(A^(n-2))，然后将它乘以u(2)。
当然，任何这样的技术都可能需要某种BigInt，否则溢出几乎得到保证。
另请注意，此技术可以进一步应用：
您可以找到A的特征向量和特征值，然后将u(2)分解为特征向量。然后，您将获得f（n）和g（n）的闭合形式。
我强烈建议您不要使用基于封闭形式的算法
几乎可以肯定，它将涉及高精度浮点计算（除非所有特征值都是整数，这是极不可能的），这从编程的角度来看至少是这种复杂性，并且通常不是恒定时间操作。当然，BigInt也都没有。因此，恒定时间算法通常是不可行的，而且你可能甚至不需要O(log(n))，因为对于大多数用途来说线性足够好。
注意 这里描述的技术可以用于各种问题，并且在动态优化问题中极其有用。此外，通常人们第一次看到这一点时会留下深刻的印象;）