矩阵覆盖

题目描述:

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

思路

第一种思路

找规律
当n=1的时候 覆盖方法为1；
当n=2的时候，覆盖方法为2；
当n=3的时候,覆盖方法为3；
当n=4的时候。覆盖方法为5；大家有没有找到规律，这又是一个典型的斐波那契数列题目；

代码实现

第一种思路

public class Main {
    public static void main(String[] args) {
        System.out.println(RectCover(4));
    }
    //
    public static int RectCover(int target) {
        if(target < 1 ) return 0;
        if(target == 1) return 1;
        else if(target==2) return 2;
        else return RectCover(target-1)+RectCover(target-2);
    }
}

既然是斐波那契数列，那就还有一种写法

public class Main {
    public static void main(String[] args) {
        System.out.println(RectCover(1));
    }
    //
    public static int RectCover(int target) {
        if(target < 1 ) return 0;
        else if(target==1) return 1;
        else if (target == 2) return 2;
        else
        {
            int f = 1;
            int g = 2;
            int temp;
            while (target >=3)
            {
                target--;
                temp = g;
                g = f + g;
                f = temp;
            }
            return g;
        }
    }
}