矩形覆盖

《剑指offer》面试题10（题目二）相关题目：矩形覆盖

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

思路：设2 x n 的大矩形的覆盖方法共有f （n）种，第一个2 x 1的小矩形去覆盖大矩形最左边的时候有2种选择：横着放和竖着放。当竖着放的时候，剩余2 x (n-1)的大矩形共有f（n-1）种方法覆盖；当2 x 1的小矩形横着放在左上角的时候，必须有一个2 x 1的矩形放在左下角，剩余2 x (n-1)的大矩形共有f（n-2）种方法覆盖。故总共的覆盖方法f（n）= f（n-1）+ f（n-2）。

代码如下：

public int rectangleCover(int n) {
    if (n <= 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else if (n == 2) {
        return 2;
    } else {
        int num1 = 1;
        int num2 = 2;
        int temp = 0;
        for (int i = 3;i <=n;i++) {
            temp = num1 + num2;
            num1 = num2;
            num2 = temp;
        }
        return temp;
    }
}