10.矩形覆盖

佚名 5年前 (2019-04-13) 随笔 977人围观抢沙发百度已收录

题目描述：

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

思路分析：

当n小于1的时候，共有0种方法，当n=1时，有一种方法。当n=2的时候有两种方法。当n=n时。如果第一块放置2*1的，那么问题转化为求n为n-1。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

1
1

如果第一块放置1*2，那么问题就转化为n为n-2。

1	1
0	0

代码：

public class Solution {
    public int RectCover(int target) {
         if(target<1)
             return 0;
        else if(target==1)
            return 1;
        else if(target==2)
            return 2;
            return RectCover(target-1)+ RectCover(target-2);
    }
}