首页 > 试题广场 >

矩形覆盖

[编程题]矩形覆盖
  • 热度指数：609707 时间限制：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
算法知识视频讲解
添加回答
推荐
Follow头像 Follow
依旧是斐波那契数列
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)
Python
华科平凡头像 华科平凡

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)
黄涛头像 黄涛
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)
我的头很铁1头像 我的头很铁1 
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)
Python
最小森林头像 最小森林 
# -*- 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)
格子军团0号菜鸡头像 格子军团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)
C/C++
牛客2030759号头像 牛客2030759号
第一块有两种方式：横着放和竖着放
横这放对应为发f(n-2);
竖着放下一步的放方法为f(n-1);
所以总的放的方法为f(n)=f(n-1)+f(n-2);
发表于 2016-08-27 14:46:20 回复(1)
AndyJee头像 AndyJee
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)
Java
和IT死磕到底头像 和IT死磕到底
用若干个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)
Howie59头像 Howie59 
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)
geeeeeeker头像 geeeeeeker 
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)
Java
牛客小健健头像 牛客小健健 
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)
Python 3
时光他与猫头像 时光他与猫
# -*- 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)
Python 3
阿司匹林Yo头像 阿司匹林Yo 
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)
牛客264066192号头像 牛客264066192号
主要分享一个理解思路。
对于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)
C/C++
陌小桑Vec头像 陌小桑Vec
其实类似于斐波那契数列，只不过稍微变了一下 
class Solution {
public:
    int rectCover(int number) {
        if (number == 0) return 0;
        if (number == 1) return 1;
        if (number == 2) return 2;
        return rectCover(number - 1) + rectCover(number - 2);
    }
};


发表于 2021-07-01 22:11:48 回复(0)
JavaScript
IPzzzi头像 IPzzzi 
function rectCover(number)
{
    // write code here
    var dp = [];
    if(number == 0){
        return 0;
    }
    dp[1] = 1;
    dp[2] = 2;
    for(var i = 3;i<=number;i++){
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[number];
    
}

发表于 2021-03-16 18:01:44 回复(0)
Java
tornado123头像 tornado123
类似于斐波那契数列的递归求解（也可以用递推） 
    public int rectCover(int target) {
        //target == 1 时，只有竖放的一种可能；
        //target == 2 时，再 2 * 2 大矩形中有横放和竖放两种方法； ……
        if (target <= 2){
            return target;
        }
        return rectCover(target - 1) + rectCover(target - 2);
    }


发表于 2020-10-04 11:51:45 回复(0)
提交观点

问题信息

动态规划 递归
来自：开发工程师&系统架构高...
难度：
1383条回答 150523浏览

热门推荐

通过挑战的用户

查看代码

相关试题

矩形覆盖

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号