首页 > 试题广场 >

矩形覆盖

[编程题]矩形覆盖
  • 热度指数:607075 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
我们可以用 2*1 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 2*1 的小矩形无重叠地覆盖一个 2*n 的大矩形,从同一个方向看总共有多少不同的方法?

数据范围:
进阶:空间复杂度 ,时间复杂度

注意:约定 n == 0 时,输出 0

比如n=3时,2*3的矩形块有3种不同的覆盖方法(从同一个方向看):


输入描述:
2*1的小矩形的总个数n


输出描述:
覆盖一个2*n的大矩形总共有多少种不同的方法(从同一个方向看)
示例1

输入

0

输出

0
示例2

输入

1

输出

1
示例3

输入

4

输出

5
推荐
依旧是斐波那契数列
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 回复(87)

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

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

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 回复(11)
分析:
(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)
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||target==1||target==2)
            return target;
        else
            return rectCover(target-1)+rectCover(target-2);
    }
}

发表于 2020-02-15 00:44:32 回复(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)
# -*- coding:utf-8 -*-
class Solution:
    def rectCover(self, number):
        # 分析:https://uploadfiles.nowcoder.com/images/20160616/716804_1466088939214_DB8DE8E90C58DADF4C1048A7B110E8E5
        # 这个题是斐波那契数列,分析可以看上面的大神的分析,我没想起来。
            # 应该用递归实现 ,但是python递归太慢 超时,应该用非递归实现:
        if number == 0:
            return 0
        f0 = 0
        f1 = 1
        NEXT = 0
        i = 0 
        while i < number:
            NEXT = f0 +f1 # 下一个值 是前两个的和
            f0 = f1 # f0 往前走一步
            f1 = NEXT # f1 往前走一步
            i += 1 
        return NEXT

发表于 2018-04-19 21:12:01 回复(2)
思路:
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)
第一块有两种方式:横着放和竖着放
横这放对应为发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) {
int A[number+1];
        A[0]=0;
        A[1]=1;
        A[2]=2;
        for(int i=3;i<=number;i++)
            A[i]=A[i-1]+A[i-2];
        return A[number];
}
};
发表于 2015-04-09 16:22:58 回复(0)
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)
用若干个2*1大小的矩形去无重叠覆盖2*n大小的矩形:
当n=1时,有1种方法;
当n=2时,有2种方法;
当n=3时,有3种方法;
当n=4时,有5种方法;
从题目所给条件不难看出,这是一个斐波那契数列的规律,但是我们如何从题目场景中进行推导呢?
我们从n=N出发:
①当左边第一块2*1的矩形横向放置时(红色填充部分),其下面的矩形只有一种情况(红色边框部分);
因此,2*N的矩形被分割成两部分:2*2 和 2*(N-2);
              
      
      
     
      
        
       
         









②当左边第一块2*1的矩形竖向放置时(红色填充部分),整个矩形被分成左右两部分
2*N的矩形被分割成两部分:2*1 和 2*(N-1);

        
        
        
         
         
         
        
         









综上,我们可以发现,2*N的矩形可以看做2*(N-1)矩形覆盖方式+2*(N-2)矩形覆盖方式
                                    即       f(N)=f(N-1)+f(N-2)
代码:
public class Solution {
    public int rectCover(int target) {
        if(target<=2){
            return target;
        }
        int pre=1;
        int cur=2;
        for(int i=3;i<=target;i++){
            cur+=pre;
            pre=cur-pre;
        }
        return cur;
    }
}


发表于 2020-11-19 12:11:55 回复(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)
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 回复(37)
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)
public class Solution {
    public int rectCover(int target) {
        if(target == 0)return 0;
        if(target == 1)return 1;
        if(target == 2)return 2;
        return rectCover(target -1) + rectCover(target -2);
    }
}

发表于 2022-04-10 20:11:28 回复(0)
# -*- coding:utf-8 -*-
# 我这样做算是动态规划吗?

class Solution:
    def rectCover(self, number):
        # write code here
        if number == 0:
            return 0
        if number == 1:
            return 1
        if number >= 2:
            a = 1
            b = 1
            ret = 0
            for i in range(number-1):
                ret = a + b
                b = a
                a = ret
            return ret
发表于 2021-08-22 13:41:59 回复(0)
class Solution:
    def rectCover(self, number):
        if number <= 2:
            return number
        num1, num2 = 1, 2
        for _ in range(number-2):
            num2 += num1
            num1 = num2 - num1
        return num2

发表于 2021-07-31 08:39:07 回复(0)
主要分享一个理解思路。
对于n个小矩形拼成2*n矩形,假设它有f(n)种,那么这f(n)种的形式肯定是不同的(废话),而对于这个f(n)种,它们当中的任意一种,必然满足以下条件中的一个:
1)最右侧为一个竖着的小矩形,将这个竖着的小矩形抹去,则剩下的就是一个2*(n-1)的矩形;
2)最右侧为两个横着的小矩形,将这两个横着的小矩形抹去,则剩下的就是一个2*(n-2)的矩形。
显然的是,凡是归类到1)中去的,它们擦除最右侧小矩形后,剩下的2*(n-1)肯定是不一样的(如果一样,那加上最右侧岂不也是一样),而2)中的同理。
继续很显然的是,对于1)的情况,必然有f(n-1)种,而对于2)的情况,会有f(n-2)种。
因此结论很显然的是,f(n) = f(n-1) + f(n-2),当然,条件很显然的是,n>2。
发表于 2021-07-13 22:46:50 回复(0)