【剑指offer】10：矩形覆盖

时间:2021-04-17 zhang十六人气:2

题目描述：

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

解题思路：

①方法一

对于这种题没有思路怎么办？可以先从最简单的情况开始考虑：

显然，当n = 1时，只有一种方法

当n = 2时，如图有两种方法

当n = 3时，如图有三种方法

当我们做到这里总会出现错觉，是不是n等于几就是有几种方法呢？我们再接着来尝试：

当n = 4时，如图有五种方法。

做到这里基本上会确定就是斐波拉契数列了，可以接着验证，这里不做赘述

②方法二

可以先把2X4的覆盖方法记为f(4)【如上图n=4时的第一个图】，用1X2的小矩形去覆盖时，有两种选择：横着放或者竖着放。当竖着放时，右边还剩下2X3的区域。很明显这种情况下覆盖方法为f(3)。当横着放时，1X2的矩形放在左上角，其下方区域只能也横着放一个矩形，此时右边区域值剩下2X2的区域，这种情况下覆盖方法为f(2)。所以可以得到：f(4)=f(3)+f(2)，不难看出这仍然是斐波那契数列。

特殊情况：f(1)=1，f(2)=2

代码实现

（C实现）：

int rectCover(number)
{
    // write code here
    int fir = 1, sec = 2, res;
    if (number <= 0 || number == 1 || number == 2) return number;
    for (int i = 2; i <number; i++) {
        res = fir + sec;
        fir = sec;
        sec = res;
    }
    //res = rectCover(number - 1) + rectCover(number - 2);  递归方式
    return res;
}

（JavaScript实现）：

function rectCover(number)
{
    // write code here
    var fir = 1, sec = 2, res;
    if (number <= 0 || number == 1 || number == 2) {
        return number;
    }
    for (var i = 2; i <number; i++) {
        res = fir + sec;
        fir = sec;
        sec = res;
    }
    //res = rectCover(number - 1) + rectCover(number - 2);  递归方式
    return res;
}

加载全部内容