题目：
If we want to build a brick wall out of the usual size of brick which has a length twice as long as its height, and if our wall is to be two units tall, we can make our wall in a number of patterns, depending on how long we want it. From the figure one observe that:
- There is just one wall pattern which is 1 unit wide — made by putting the brick on its end.
- There are 2 patterns for a wall of length 2: two side-ways bricks laid on top of each other and two bricks long-ways up put next to each other.
- There are three patterns for walls of length 3.
How many patterns can you find for a wall of length 4? And, for a wall of length 5?
题意：
有长高宽为1:2的砖块，忽略其厚度，题目中单个砖块长=1，所以宽=2。用不同的堆叠形式组成墙，墙的横向视为长（length）,竖向视为高（height），保持高度始终为2。
- 当要求砖块堆长度为1时，有一种堆叠形式；
- 当要求长度为2时，有两种堆叠形式；
- 当要求长度为3时，有三种堆叠形式；
问：当要求砖墙长度为4时，有多少种堆叠形式。如果长度为5，又有多少种？推广至长度n，又有多少种？
题解：
这是一道数学题，也是UVa OJ上的一道算法题，但是网上很多只给出代码，不讲证明过程。我在英国萨里大学 (University of Surrey) 数学学院的网站上找到了完整思路，将其整理如下：
将砖墙长度记为n，相应砖墙的堆叠形式的总数记位\(f(n)\)。根据题目给出的图样示例可以得知：
- \(f(1)=1\)
- \(f(2)=2\)
- \(f(3)=3\)
同时，也可以发现两种基本的堆叠形式：
所有的砖墙都可以被视为图1两种形式的排列组合。我们将图1左侧的砖块堆叠形式记为“基本形式1”，其长度为1；右侧记为“基本形式2”，长度为2。
根据题目中的图样示例可以看出，基本形式1和2分别存在于length=1和length=2的堆叠形式中。
我们进一步推广分析，当\(n>2\)时，我们可以发现\(f(n)\)的所有堆叠形式可以划分为下面两种情况：
- 在长度为\(n-1\)的所有堆叠形式的砖墙最右侧，追加基本形式1，然后得出砖墙形式总数仍为\(f(n-1)\)：
- 在长度为\(n-2\)的所有堆叠形式的砖墙最右侧，追加基本形式2，得出砖墙形式总数仍为\(f(n-2)\)：
当然，也可以选择在砖墙最左、或中间任何位置插入，本文选择最右侧仅仅是为了方便描述。
在分解成上面两种情况之后，应该就可以很容易地看出：当\(n>2\)时，\(f(n)\)可以视为这两种情况之和，即：$$f(n)=f(n-1)+f(n-2)\hspace{3mm}(n>2)$$
结合\(n=1\)，\(n=2\)的情况得出最终结果：
$$f(1)=1, \\ f(2)=2, \\ f(n)=f(n-1)+f(n-2)\hspace{3mm}(n>2).$$
是不是特别像Fibonacci数列的递归定义（注意标准的Fibonacci数列是从0，1开始的）。