剑指offer-10、矩阵覆盖

题目描述

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

思路及解答

我们需要用若干个2×1的小矩形（可以横放或竖放）无重叠地覆盖一个2×n的大矩形，求总共有多少种不同的覆盖方法。例如当n=3时，共有3种覆盖方法。
通过观察小规模案例，我们可以发现：

• n=1时，只有1种方法（竖放）
  
• n=2时，有2种方法（两个竖放或两个横放）
  
• n=3时，有3种方法
  
• n=4时，有5种方法
  

显然，这形成了一个类似斐波那契数列的规律：f(n) = f(n-1) + f(n-2)。这一题其实和上面青蛙跳台阶和斐波那契数列是一样的，变的只是场景。
递归

递归是解决这类问题最直观的方法。对于2×n的矩形，我们考虑第一块小矩形的放置方式：

• 如果竖着放，则剩下的部分是2×(n-1)的矩形，有f(n-1)种方法
  
• 如果横着放，则下方也必须横放一块，剩下的部分是2×(n-2)的矩形，有f(n-2)种方法
  

因此，总方法数为这两种情况之和：f(n) = f(n-1) + f(n-2)，这正是斐波那契数列的递推关系
[code]public class Solution {    public int rectCover(int n) {        if (n