首页 > 试题广场 > 矩形覆盖
[编程题]矩形覆盖
  • 热度指数:407679 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?
推荐
依旧是斐波那契数列
2*n的大矩形,和n个2*1的小矩形
其中target*2为大矩阵的大小
有以下几种情形:
1⃣️target <= 0 大矩形为<= 2*0,直接return 1;
2⃣️target = 1大矩形为2*1,只有一种摆放方法,return1;
3⃣️target = 2 大矩形为2*2,有两种摆放方法,return2;
4⃣️target = n 分为两步考虑:
        第一次摆放一块 2*1 的小矩阵,则摆放方法总共为f(target - 1)















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






× ×






代码:
public class Solution {
    public int RectCover(int target) {
      if(target  <= 1){
			return 1;
		}
        if(target*2 == 2){
            return 1;
        }else if(target*2 == 4){
            return 2;
        }else{
            return RectCover((target-1))+RectCover(target-2);
        }
    }
}

编辑于 2015-12-12 12:08:02 回复(76)
public class Solution {
    public int RectCover(int target) {
        if (target < 1) {
            return 0;
        } else if (target == 1 || target == 2) {
            return target;
        } else {
            return RectCover(target-1) + RectCover(target-2);
        }
    }
}
走过的弯路:
开始只是简单地将 n 分成奇、偶讨论,并将 2*2 作为基本单元。测试后通不过,代码就不贴出来献丑了。
思路分析:
痛定思痛,还是不能够贪小便宜。用归纳法归纳如下,
(1)当 n < 1时,显然不需要用2*1块覆盖,按照题目提示应该返回 0。
(2)当 n = 1时,只存在一种情况。

(3)当 n = 2时,存在两种情况。

(4)当 n = 3时,明显感觉到如果没有章法,思维难度比之前提升挺多的。

... 尝试归纳,本质上 n 覆盖方法种类都是对 n - 1 时的扩展。
可以明确,n 时必定有 n-1时原来方式与2*1的方块结合。也就是说, f(n) = f(n-1) + ?(暂时无法判断)。
(4)如果我们现在归纳 n = 4,应该是什么形式?
4.1)保持原来n = 3时内容,并扩展一个 2*1 方块,形式分别为 “| | | |”、“= | |”、“| = |”
4.2)新增加的2*1 方块与临近的2*1方块组成 2*2结构,然后可以变形成 “=”。于是 n = 4在原来n = 3基础上增加了"| | ="、“= =”。
再自己看看这多出来的两种形式,是不是只比n = 2多了“=”。其实这就是关键点所在...因为,只要2*1或1*2有相同的两个时,就会组成2*2形式,于是就又可以变形了。
所以,自然而然可以得出规律: f(n) = f(n-1) + f(n-2), (n > 2)。

如果看了这一套理论还存在疑惑。可以尝试将题目改成1*3方块覆盖3*n、1*4方块覆盖4*n。
相应的结论应该是:
(1)1 * 3方块 盖3*n区域:f(n) = f(n-1) + f(n - 3), (n > 3)
(2) 1 *4 方块 盖4*n区域:f(n) = f(n-1) + f(n - 4),(n > 4)
更一般的结论,如果用1*m的方块覆盖m*n区域,递推关系式为f(n) = f(n-1) + f(n-m),(n > m)。
发表于 2016-08-21 02:27:39 回复(33)

在分析前不知道是什么序列,所以先看了n=1,n=2,n=3,n=4的情况摸索规律,主要是看 n 和 n-1 的隐含联系。(2*1 指 长宽)
图片说明

发表于 2017-07-18 20:34:33 回复(20)

编辑于 2016-06-16 22:56:30 回复(25)

假设:n块矩形有f(n)种覆盖方法。进行逆向分析,要完成最后的搭建有两种可能。

第一种情况等价于情形1中阴影部分的n-1块矩形有多少种覆盖方法,为f(n-1);

第二种情况等价于情形2中阴影部分的n-2块矩形有多少种覆盖方法,为f(n-2);

故f(n) = f(n-1) + f(n-2),还是一个斐波那契数列。。。。

且f(1) = 1, f(2) = 2,代码如下
public class Solution {
    public int RectCover(int target) {
		if(target <= 0){
            return 0;
        }
        if(target == 1){
            return 1;
        }
        if(target == 2){
            return 2;
        }
        int first = 1;
        int second = 2;
        int result = 0;
        for(int i = 3; i <= target; i++){
            result = first + second;
            first = second;
            second = result;
        }
        return result;
    }
}

编辑于 2017-08-16 13:43:32 回复(8)

分享一个斐波那契数列的迭代算法,当问题规模较大时,该迭代算法效率远高于递归

class Solution {
public:
    int rectCover(int number) {
        if ( number < 1 ) return 0;
        int g = 1, f = 2;
        while ( --number ) {
            f = f + g;
            g = f - g;
        }
        return g;
    }
};
发表于 2018-01-20 14:46:57 回复(6)

python solution:



class Solution:
    def rectCover(self, number):

        res = [0,1,2]
        while len(res) <= number:
            res.append(res[-1] + res[-2])
        return res[number]

发表于 2017-10-13 22:00:13 回复(7)
逆向分析
应为可以横着放或竖着放,多以f(n)可以是2*(n-1)的矩形加一个竖着放的2*1的矩形或2*(n-2)的矩形加2横着放的,即f(n)=f(n-1)+f(n-2)
当到了最后,f(1)=1,f(2)=2

发表于 2015-05-10 20:56:09 回复(6)
这个跟第一个跳台阶的题原理是一样的吧?要么一次加1,要么一次加2?
发表于 2015-04-09 11:11:50 回复(5)
这里必须要吐槽一下,target为0的时候怎么就返回1了???出题者你出来解释一下,我保证不打残你。。。

/**
	 * 其实就是一个斐波那契数列,满足公式:d(n) = d(n-1) + d(n-2) 
	 * @param target
	 * @return
	 */
	public int RectCover(int target) {
		int tempNum = 1;
		int result = 2;
		
		if (target == 0) {
			return 1;
		}
		
		if (target == 1 || target == 2) {
			return target;
		}
		
		int count = 2;
		while (count < target) {
			result += tempNum;
			tempNum = result - tempNum;
			count ++;
		}
		return result;
	}

发表于 2015-11-06 20:07:26 回复(17)
分析:
(1) n等于1时,总共有1种方法。

(2) n等于2时,总共有2种方法。
2*1的矩形,横着或竖着分别一种。

(3) n等于3时,总共有3种方法。
1) 2*1的矩形全部竖着放;  2)第一列 2*1的矩形竖着放,后面两列横着放两个2*1的矩形; 3)前面两行横着放两个2*1的矩形,最后一列竖着放一个2*1的矩形。

.............................
我们可以看到,由于2*1的小矩形可以横着放也可以竖着放,当n=3的时候,在n=2的基础上其实只有一种放法了,就是把第三个2*1的小矩形竖着放,在n=1的基础上,把第二个和第三个2*1的小矩形横着放(有人会说为什么竖着放两个不算,这已经包括在n=2的情况下了)。所以抽象表示就是f(3)=f(2)+f(1)。也还是裴波那契的思想。不过如果递归复杂度比较高,因此我们还是用“跳台阶”的方法来实现。

程序如下:
class Solution {
public:
int rectCover(int number) {

int result[3]={0,1,2};
if(number<3)
return result[number];
int frontRectar1=1;                         //矩形rectar
int frontRectar2=2;
int sumRectar;
for(int i=3;i<=number;i++)
{
sumRectar=frontRectar1+frontRectar2;
frontRectar1=frontRectar2;
frontRectar2=sumRectar;
}
return sumRectar;
}
};
编辑于 2017-06-23 21:46:51 回复(3)
我们对算法模型做些简化,我们知道,只可以放置两种类型的小矩形,一种是竖着放的2*1矩形,另一种是两块横着放的2*1矩形上下放置形成的2*2正方形,而题目要放置的是2*n的大矩形。
我们将上面模型映射到一维,即是我们有一条长度为n的线段,现在要么放置长度为1,要么放置长度为2的线段,请将该线段填满。
这让我想起了走阶梯的题目,一个n级阶梯,每次要么走一级要么两级,请问有多少种方法。
综上分析,可知,
n = 1时, f(n) = 1;
n = 2时, f(n) = 2;
n > 2时,f(n) = f(n - 1) + f(n - 2);
标准的斐波那契数列,故可用斐波那契数列解决,代码如下,不足之处请大家多多指点:
class Solution {
public:
    int rectCover(int number) {
        if(number < 1)
            return 0;
        if(number < 3)
            return number;
        int i;
        int f = 1, g = 2;
        for(i = 2; i < number; ++i){
            g += f;
            f = g - f;
        }
        return g;
    }
};

发表于 2018-07-19 08:04:24 回复(0)
class Solution {
public:
 int rectCover(int number) {
  int s1=0,s2=1;
  while(number-- > 0)
  {
   int t = s2;
   s2 += s1;
   s1 = t;
  }
  return s2;
 }
};
发表于 2015-04-07 16:21:35 回复(0)
public class Solution {
    public int RectCover(int target) {
        if(target==0)
            return 1;
		if(target<=3)
            return target;
        int p = 3;
        int pp = 2;
        for(int i = 4;i<=target;i++){
            int c = p+pp;
            pp = p;
            p = c;
        }
        return p;
    }
}

发表于 2016-04-15 02:11:19 回复(0)
第一块有两种方式:横着放和竖着放
横这放对应为发f(n-2);
竖着放下一步的放方法为f(n-1);
所以总的放的方法为f(n)=f(n-1)+f(n-2);
发表于 2016-08-27 14:46:20 回复(1)
class Solution {
public:
    int rectCover(int number) {
        if(number<=0)
            return 1;
        int  temp1=1,temp2=1,temp3=1;
        while(--number){
            temp3=temp1+temp2;
            temp1=temp2;
            temp2=temp3;
        }
        return temp3;
    }
};
类似于斐波那契数列
发表于 2015-08-06 14:58:27 回复(0)
public class Solution {
    public int RectCover(int target) {
        int a = 0;
        int b = 1;
        if(target == 0){
            return 0;
        }
        if(target == 1){
            return 1;
        }
        if(target == 2){
            return 2;
        }
        while(target-->0){
            b = a + b;
            a = b - a;
        }
        return b;
    }
}
dp思想
发表于 2018-08-03 12:01:49 回复(0)
思路:
f(1) = 1;
f(2) = 2;
当n>2时,画图可知,第一块小矩形可横放和竖放。横放后剩余的长度为n-2,竖放后剩余的长度为n-1。
所以:f(n) = f(n-1) + f(n-2);  (n > 2)
public class Solution {
    public int RectCover(int target) {
        if (target <= 2) {
            return target;
        }
        int one = 1;
        int two = 2;
        int result = 0;
        for (int i = 3; i <= target; i++) {
            result = one + two;
            one = two;
            two = result;
        }
        return result;
    }
}

编辑于 2018-03-02 21:39:26 回复(0)
其实就是简单的斐波那契数列, f(n) = f(n-1) + f(n-2),
因此无论是用递归法或者直接法都很简单。但是递归效率很低。
class Solution {
public:
    //方法一:递归,代码简单,但是耗时长,约500ms
    int rectCover(int number) {
        if(number <= 2) return number;
        else return rectCover(number-1) + rectCover(number-2);
    }

    //方法二:非递归,复杂度低,速度快,只要3ms
    int rectCover(int number) {
        if(number <= 2) return number;
        int a=1, b=2, cnt = 2;
        while(cnt < number)
        {
            b += a;
            a = b - a;
            cnt ++;
        }
        return b;
    }
};
发表于 2017-11-22 22:30:17 回复(0)
Java
public class Solution {
    public int RectCover(int target) {
        int i=0;
        int[] temp={1,1};
        while(i++<target/2){
            temp[0]+=temp[1];
            temp[1]+=temp[0];
        }
        return temp[target%2];
    }
}
发表于 2015-10-24 15:09:41 回复(1)
c#
class Solution
{
    public int rectCover(int number)
    {
       
        if(number<0){return -1;}
        if(number==0){return 0;}
        if(number==1){return 1;}
        if(number==2){return 2;} 
        //循环方法
        int[] sums=new int[number+1];
        sums[0]=0;
        sums[1]=1;
        sums[2]=2;
        for(int i=3;i<=number;i++){
            sums[i]=sums[i-1]+sums[i-2];
        }
        return sums[number];
       //递归(循环调用方法更快) 
        /*return rectCover(number-1)+rectCover(number-2);*/
    }
}


编辑于 2019-10-07 15:01:37 回复(0)