剑指 Offer - 10 - 矩形覆盖

Question

题目

和 POJ - 2506. Tiling 类似。

我们可以用 2*1 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 2*1 的小矩形无重叠地覆盖一个 2*n 的大矩形，总共有多少种方法？

解析

覆盖 2 * n （ 2 代表行， n 代表列）的时候，先看看假设前面已经覆盖 2 * (n-2) 之后，到 2 * n 之间还有多少种覆盖法：

• 后面两个只有两种覆盖方法，一种是全部竖着放（实际上是从 2 * (n-1) 来的），这里注意不要认为还有一种情况是放置两个竖的，实际上放好 n-1 的情况中已经包含了那种情况；
• 另一种就是全部横着放，也就是 n-2 到 n 之间横着放两块 1 * 2 的矩形，如图 (2) ；
• 所以 f_n= f_n-1 + f_n-2 ，和跳台阶问题（第二题) 完全一样。

由于代码和跳台阶问题（剑指 Offer08 跳台阶) 一模一样，就不放重复的代码了。