剑指Offer - 10 - 矩形覆盖.md

剑指Offer - 10 - 矩形覆盖

题目链接

https://www.nowcoder.com/practice/72a5a919508a4251859fb2cfb987a0e6?tpId=13&tqId=11163&tPage=1&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking

题目

和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跳台阶)一模一样，就不放重复的代码了。