矩形覆盖

发表于 | 更新于 | 分类于 | 阅读次数： | 阅读次数：
本文字数： 621 | 阅读时长 ≈ 1 分钟

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


解析：

（1）当 n = 1时，只存在一种情况：

（2）当 n = 2时，存在两种情况：

（3）当 n >= 3时，分为两步考虑：
　　（3.1） 第一次摆放一块 2*1 的小矩阵，则余下的摆放方法总共为f(target - 1)

　　（3.2）第一次摆放一块1*2的小矩阵，则余下的摆放方法总共为f(target-2)
　　因为，摆放了一块12的小矩阵（用√√表示），对应下方的12（用××表示）摆放方法就确定了，所以为f(targte-2)

　　故得出结论：f(target) = f(target - 1)+ f(target - 2)

代码：

1
2
3
4
5
6
7
8
9
10
public class Solution {
    public int RectCover(int target) {
        if(target<=0)
            return 0;
        else if(target==1 || target==2)
            return target;
        else
            return RectCover(target-1)+RectCover(target-2);
        }
}
---------------- The End ----------------
0%