首页 > 试题广场 >

矩形覆盖

[编程题]矩形覆盖

热度指数：609707 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

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

数据范围： $0 \le n \le 38 \$
进阶：空间复杂度 $O(1)\$ ，时间复杂度 $O(n)\$

注意：约定 n == 0 时，输出 0

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

输入描述:

2*1的小矩形的总个数n

输出描述:

覆盖一个2*n的大矩形总共有多少种不同的方法(从同一个方向看)

示例1

输入

输出

示例2

输入

输出

示例3

输入

输出

算法知识视频讲解

推荐

依旧是斐波那契数列

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

牛客541273514号

# -*- coding:utf-8 -*-
class Solution:
    def rectCover(self, number):
        # write code here
        res=[0,1,2,3]
        if number<=3:
            return res[number]
        else:
            for i in range(4,number+1):
                res.append(res[i-1]+res[i-2])
            return res[number]

发表于 2021-04-11 23:45:51 回复(0)

Python

牛客313692148号

# -*- coding:utf-8 -*-
class Solution:
def rectCover(self, number):
# write code here
if number<2:
return number
a, b = 0,1
for _ in range(number):
a,b = b,a+b
return b

发表于 2021-03-29 18:29:45 回复(0)

Python

张默雨

这一题其实就相当于有n个台阶，我们可以从图例的n=3中看到，要么三个矩形竖着靠一起，每个矩形竖着就相当于迈一步，每一步消耗一个矩形。或者两个矩形拼接在一起，这就相当于我们一次迈两步，同时消耗两个矩形。那么我们想迈n步的话，要么用两个矩形消耗来一次迈两步，要么就每一次都只消耗一个矩形来迈一步，这就转化成简单的迈台阶的问题，F(n)=F(n-1)+F(n-2)即可求解：

class Solution:

def rectCover(self, number):
# write code here
if number == 1 or number == 2:
return number
first, second = 1, 2
target = 0
for i in range(2, number):
target = first + second
first = second
second = target
return target

发表于 2021-02-22 22:20:30 回复(0)

Python

牛客1349号

python 实现

原理还是斐波那契数列

# -*- coding:utf-8 -*-
class Solution:
    def rectCover(self, number):
        # write code here
        if number in [0, 1, 2]:
            return number
        res = [1, 2]
        for i in range(2, number):
            res.append(res[-1]+res[-2])
        
        return res[-1]

发表于 2020-08-04 16:09:46 回复(0)

Python

DDooo

# -*- coding:utf-8 -*-
class Solution:
    def rectCover(self, number):
        # write code here
        array = [0,1,2]
        if number < 3:
            print array[number]
        for i in range(3,number+1):
            array.append(array[i-2]+array[i-1])
        return array[number]

其实也是斐波那契数列，需要总结出以下规律：

n=0,1,2,3,4,5.....时，对应的组合方法有：0,1,2,3,5,8,13.....种。

发表于 2020-07-23 16:51:12 回复(0)

Python

牛客770473387号

# -*- coding:utf-8 -*-
class Solution:
def rectCover(self, number):
if number == 0:
return 0
elif number == 1:
return 1
else:
list = [0,1]
for a in range(number):
x = list[-1]
y = list[-2]
new_value = x+y
list.append(new_value)

return new_value


# write code here

发表于 2020-06-15 20:30:54 回复(0)

Python

学习了嘛嘛！！

有没有大佬讲讲为啥会超出时间

发表于 2020-06-03 22:03:27 回复(0)

Python

201905242154668

矩形覆盖(理论+python实现)

1.理论

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

比如n=3时，2*3的矩形块有3种覆盖方法：

思路分析

对于这种类型的题目，进行规律分析得出其通项公式是比较高效的方式。

规律分析
f(1)=1
f(2)=2
f(3)=3,   f(3)=f(2)+f(1)
f(4)=5,   f(4)=f(3)+f(2)

通过规律分析，这道看似复杂的题目，其实就是斐波那契数列的应用，也是一个递归性问题，本编程题的通项公式如下：

$f(1)=1$ ) $f(2)=2$ ) $f(n)=f(n-1)+f(n-2),n>=3$

python实现

问题的复杂是相对的，如果你通过思考分析出问题的根源或规律，那么问题就可以简单化。反之，没有进行思考和分析，任何问题都会被复杂化，因此进行思考和分析是直观重要的。

# -*- 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:
            return 2
        # -------------------------------
        # 实际应用
        fone,ftwo,total=1,2,0
        for i in range(3,number+1):
            # 规律
            #f(1)=1
            #f(2)=2
            #f(3)=3, f(3)=f(2)+f(1)
            #f(4)=5, f(4)=f(3)+f(2)
            total=fone+ftwo
            fone,ftwo=ftwo,total
        return total

编辑于 2020-02-19 15:43:47 回复(0)

Python

燃墨

斐波那契数列变形，理解了就好做了

思路：

n 取值1,2时，分别有1,2两种形式

当 n 大于2时，可这么理解：

当 n 取3时，即n=2时的方式 + 还剩一个位置只有一种方式

当 n 取4时，即n=2时的方式 + 还剩两个个位置有2种方式，即前两种与后两种组合

后续同理，以步长为 2 将你分组，最后结果就是各组组合的所有结果

class Solution:
    def rectCover(self, number):
        # write code here
        if number == 0:
            return 0
        elif number == 1:
            return 1
        elif number == 2:
            return 2
        else:
            a = 1
            b = 2
            for i in range(3,number+1):
                a,b = b,a + b  
            return b

编辑于 2019-12-17 23:36:55 回复(0)

Python

牛客882602551号

# -*- 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:
            return 2
        a = 2
        b = 1
        while number > 2:
            a = a + b 
            b = a - b 
            number = number - 1
        return a

测试通过

斐波那契数列

编辑于 2019-12-13 20:06:09 回复(0)

Python

吕营

Python Soulution:

# -*- coding:utf-8 -*-
class Solution:
    def rectCover(self, number):
        # write code here
        a = 0
        b = 1
        if number == 0:
            return 0
        for i in range(number):
            c = b
            b = a+c
            a = c 
        return b

编辑于 2019-12-06 20:15:42 回复(0)

Python

天山剑客

# -*- coding:utf-8 -*-
# 斐波那契数列变形


class Solution:
    def rectCover(self, number):
        # write code here
        a = 0
        b = 1
        i = 0
        if number == 0:
            return 0
        while i < number:
            a, b = b, a + b
            i += 1

        return b

发表于 2019-11-30 20:00:04 回复(0)

Python

秋水中的鱼

找规律,然后用动态规划。每次都是少前一块的情况加一块竖的，或者少前两块的情况加两块横的。

# -*- 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:
            return 2
        dp=[0 for i in range(number+1)]
        dp[1]=1
        dp[2]=2
        for i in range(3,number+1):
            dp[i]=dp[i-2]+dp[i-1]
        return dp[-1]

发表于 2019-10-17 18:52:57 回复(0)

Python

www_helloworld_cn

和上n级楼梯一样，可以一次盖1格（长的方向）
------------
|O| | | |……
|O| | | |……
------------
也可以一次盖两格
------------
|O|O| | |……
| | | | |……
------------
盖两格的情况，因为要全覆盖，所以下面的2*1必须和它对齐。
------------
|O|O| | |……
|O|O| | |……
------------

代码如下：

# -*- coding:utf-8 -*-
class Solution:
    def rectCover(self, number):
        # write code here
        l = [0, 1, 2]
        for i in xrange(3, number+1):
            l.append(l[-1]+l[-2])
        return l[number]

发表于 2019-10-09 19:12:37 回复(0)

Python

总有几个刁民想要害朕

# -*- coding:utf-8 -*-
class Solution:
    def rectCover(self, number):
        # write code here
        if number == 0:
            return 0
        f = [1,1]
        while number - 1 > 0 :
            f.append(f[-1]+f[-2])
            number =number -1 
        return f[-1]

Hint:

直接找规律，斐波那契数列

发表于 2019-09-20 01:07:36 回复(0)

Python

求求你别逼逼了

class Solution:
    def rectCover(self, number):
        # write code here
        if number<=2:
            return number
        else:
            res=[0,1,2]
            while len(res)<=number:
                res.append(res[-1]+res[-2])
            return res[-1]

发表于 2019-08-19 09:53:52 回复(0)

Python

201906201759268

# -*- coding:utf-8 -*-
class Solution:
def rectCover(self, number):
f = [0 for _ in range(number + 1)]
for i in range(len(f)):
if i == 0:
f[0] = 0
elif i == 1:
f[1] = 1
elif i == 2:
f[2] = 2
else:
f[i] = f[i - 2] + f[i - 1]

return f[-1]

发表于 2019-06-27 16:40:44 回复(0)

Python

半人马气质

# -*- coding:utf-8 -*-
class Solution:
    def rectCover(self, number):
        # write code here
        if number==0:
            return 0
        elif number==1:
            return 1
        elif number==2:
            return 2
        else:
            fib0=1
            fib1=2
            for i in range(number-2):
                fib2=fib0+fib1
                fib0=fib1
                fib1=fib2
            return fib2
            #return (self.rectCover(number-1)+self.rectCover(number-2))

#参考前面一位回答的斐波那切特征，十分精彩。

但是反向递归计算比较耗时，

(self.rectCover(number-1)+self.rectCover(number-2))

所以正向计算，比较迅速

发表于 2019-05-28 15:43:47 回复(0)

Python

Jonny337

Python解法，斐波那契数列问题
class Solution: 
    def rectCover(self,number):
        if number<=2:
            return number
        f1,f2=1,2
        for k in range(number-2):
            f1,f2=f2,f1+f2
        return f2

发表于 2019-05-13 00:11:07 回复(0)

Python

qibujiushi

# -*- coding:utf-8 -*-
class Solution:
def rectCover(self, number):
# write code here
fband=0
fone=1
ftwo=2
if number==0:
return 0
elif number==1:
return 1
elif number==2:
return 2
else:
i=3
while(i<=number):
fband=fone+ftwo
fone=ftwo
ftwo=fband
i=i+1
return fband

发表于 2019-04-27 23:09:47 回复(0)

提交观点

问题信息

动态规划递归

来自：开发工程师&系统架构高...

难度：

55条回答 1769收藏 150527浏览

通过挑战的用户

查看代码

温柔的山蛙

2022-10-06 01:54:59
牛客98753...

2022-09-16 13:59:28
牛客99895...

2022-09-16 11:05:05
大哥cf玩累了...

2022-09-15 22:30:26
牛客54693...

2022-09-15 22:03:32

矩形覆盖

输入描述:

输出描述:

输入

输出

输入

输出

输入

输出

矩形覆盖(理论+python实现)

1.理论

python实现

问题信息

热门推荐

通过挑战的用户

相关试题