首页 > 试题广场 >

矩形覆盖

[编程题]矩形覆盖

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

我们可以用 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)

Javascript

AAATest

function rectCover(number)
{
    // write code here
    // 
    const dp = [0,1,2] // dp[i] 为要覆盖2*i范围的操作方法
    // 注意初始化从 0, 1, ...n

    // dp[i-1], 距离dp[i] 只有一个 | 也就只有一种方法 
    // dp[i-2], 距离dp[i] 有 || 或者 = 但是上一个和 dp[i-1]一样, 所以也就只有一种方法 
    // dp[i] = dp[i-1] + dp[i-2]
    let cur = 3
    while(cur<=number){ // 因为要最后取到 dp[i] 所以要相等
        dp[cur] = dp[cur-1] + dp[cur-2]
        cur++
    }
    return dp[number]
}
module.exports = {
    rectCover : rectCover
};

发表于 2022-03-12 16:00:49 回复(0)

Javascript

牛客246205877号

function rectCover(number)
{
    let prevOne = 2,prevTwo = 1;
    if(number <= 2) prevOne = number;
    for(let i = 3;i<=number;i++){
        let curr = prevOne;
        prevOne = prevOne + prevTwo;
        prevTwo = curr
    }
    return prevOne
}
module.exports = {
    rectCover : rectCover
};

发表于 2021-09-08 14:53:12 回复(0)

Javascript

牛客477650639号

function rectCover(number)
{
    // write code here
    if(number <= 0) return 0;
    if(number == 1) return 1;
    if(number == 2) return 2;
//     return rectCover(number - 1) + rectCover(number -2);
    let f = 1;
    let g = 2;
    while(number--) {
        g += f;
        f = g - f;
    }
    
    return f;
}
module.exports = {
    rectCover : rectCover
};

发表于 2021-08-31 21:21:04 回复(0)

Javascript

周欣仪

依然是斐波拉契问题：

function rectCover(number)
{
    // write code here
    if(number<=3)
        {
            return number
        }
    var f1=2
    var f2=3
    var f=0
    for( let i=3;i<number;i++)
        {
            f=f1+f2
            f1=f2
            f2=f
        }
    return f
}
module.exports = {
    rectCover : rectCover
};

发表于 2021-08-09 17:27:37 回复(0)

JavaScript

别卷啦！

function rectCover(number)
{
    // write code here
    if(number == 0) return 0;
    const fn = (n,temp1 =1,temp2=1) => {
    if(n == 1) return temp2
    return fn(n-1, temp2,(temp1 + temp2))
    }
    return fn(number)
}

发表于 2021-07-04 20:22:58 回复(0)

JavaScript

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)

JavaScript

不进好工作不改名

function rectCover(number)
{
    // write code here
    if(number<2){return number;}
    var a=1,b=1;
    for(let i=1;i<number;i++){
        a=a+b;
        b=a-b;
    }
    return a;
}

发表于 2021-03-01 16:16:03 回复(0)

JavaScript

咚咚咚，开门，查水表

function rectCover(number)
{
    if (number == 0) return 0;
    else if (number == 1) return 1;
    else if (number == 2) return 2;
    else return rectCover(number-1) + rectCover(number-2);
}
module.exports = {
    rectCover : rectCover
};

编辑于 2020-09-13 18:05:50 回复(0)

JavaScript

萨弗拉斯的挽歌

function rectCover(number)
{
    // write code here
    //兄弟，斐波那契数列做到吐了么
    if(number){
       var arr = [1,2];
       for(let i=2;i<=number;i++){
          arr.push(arr[i-1]+arr[i-2])
       }
       return arr[number-1]
    } else {
        return 0
    }
}
module.exports = {
    rectCover : rectCover
};

编辑于 2020-08-22 21:22:08 回复(0)

JavaScript

许愿2020offer

function rectCover(number)
{
    if(number === 1 || number === 2 || number === 0) {
        return number
    } else {
        return rectCover(number - 1) + rectCover(number - 2)
    }
}
//递归的写法

发表于 2020-08-20 10:03:27 回复(0)

JavaScript

Helianthuswhite

/**
 * 我的解题思路：
 * 1.枚举结果 0, 1, 2, 3, 5, 8, .... 可以知道 n > 2 时， f(n) = f(n - 1) + f(n - 2)
 * 2.跟斐波那契数列一样的，递归和尾递归的方法这里就不写了，直接给动态规划的方法
 *
 * @param {*} number 
 */
function rectCover(number)
{
    // write code here
    let result = number ? 1 : 0;
    let temp = 1;
    while (number-- > 1) {
        result += temp;
        temp = result - temp;
    }
    return result;
}


/**
 * 评论区TOP的解题思路：
 * 很遗憾，木得了
 *
 * @param {*} number 
 */
function toprectCover(number)
{
    // write code here
}

发表于 2020-02-27 17:07:08 回复(0)

JavaScript

大贤贤

js中的动态规划

function rectCover(number)

{
// write code here
if(number<=2){
return number;
}
if(number>2){
for(var i=3,x=1,y=2,rel;i<=number;i++){
rel=x+y;
x=y;
y=rel;
}
return rel;
}
}

发表于 2019-08-09 11:17:16 回复(0)

JavaScript

一只骑单车的猫

JavaScript
动态规划，斐波那契；
递推公式：rectCover(n) = rectCover(n-1)+rectCover(n-2);

        function rectCover(number) {
            // write code here
            if(number == 0){return 0;}
            var pre=1,pos=2;
            while(--number){    // --i,先运算，后赋值，因此循环（number-1）次。
                pos+=pre;
                pre = pos - pre;
            }
            return pre;
        }

发表于 2019-05-08 21:38:43 回复(0)

JavaScript

Gliiiiiitchy

function rectCover(number)
{
    if(number <= 0){
        return 0;
    }
    
    if(number === 1){
        return 1;
    }
    
    if(number === 2){
        return 2;
    }
    
    let lastSolution = 1;
    let solution = 2;
    
    for(let i = 3; i <= number; i++){
        let newSolution = solution + lastSolution;
        
        lastSolution = solution;
        solution = newSolution;
    }
    
    return solution;
}

发表于 2019-03-10 13:46:13 回复(0)

JavaScript

不去大厂不换昵称

跟第一个跳台阶那个题很像。

假设有8个块

第1块竖着放，后面还剩7块，共f(7)种方法。

第1块横着放，后面还剩6块，共f(6)种方法。

即f(8)=f(6)+f(7) f(n)=f(n-1)+f(n-2)


	function rectCover(n)



	{



	    if(n<=2){



	        returnn;



	    }



	    let i = 2;



	    let pre = 1;



	    let current = 2;



	    let result = 0;



	    while(i++ < n){



	        result = pre + current;



	        pre = current;



	        current = result;



	    }



	    returnresult;



	}

发表于 2019-01-19 22:32:03 回复(0)

JavaScript

小小苏_su

function rectCover(number)
{
    var count = 1;
    if(number<4){
        count  = number;
    }else{
        if(number%2==0){
            count ++;  //再加一种全为2的状态，当全为2时，就不进入排列组合计算
        }
        count += getResult(number); 
    }
    //竖着不管，题目等价转化为至少一个2时，通过2和1排列组合占据n个位置
    return count;
}
function getResult(num){
    var result = 0;
    var total = 0; //1和2的总数
    var max2 = Math.floor(num/2);  //最多有对少个2
    for(var i = 1; i<=max2; i++){
        var count1 = num - 2*i;  //1的个数
        total = i + count1;
        if(count1>0){  //否则是全2的状态，已经加入了
            result += methods(total,i)/methods(i,i);
        }
    }
    return result;
}
//n表示从哪个数开始，x表示阶乘多少次
function methods(n,x){
    var res =n;
    if(x==1){
        return n;
    }else{
        for(var i=1; i<x; i++){
            res = res*(n-i);
        }
    }
    return res;
}

发表于 2018-05-30 11:26:10 回复(0)

JavaScript

求一个offer啊啊啊

feibonaqi数列
function rectCover(number) {
    // write code here
    if (number == 0) return 0;
    else if (number == 1) return 1;
    else if (number == 2) return 2;
    var pre = 1,
      next = 2;
    while (--number) {
      next += pre;
      pre = next - pre;
    }
    return pre;
  }

发表于 2018-05-28 19:07:19 回复(0)

JavaScript

优雅1217

function rectCover(number)
{
    // write code here
    if(number<3){
        return number;
    }
    var prev = 1;
    var next = 2;
    var result=0;
    for(var i=3;i<=number;i++){
        result = prev+next;
        prev = next;
        next = result;
    }
    return result;
}

发表于 2018-05-11 17:27:08 回复(0)

提交观点

问题信息

动态规划递归

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

难度：

23条回答 1791收藏 153838浏览

通过挑战的用户

查看代码

温柔的山蛙

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

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

2022-09-16 11:05:05
大狗叫叫

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

2022-09-15 22:03:32

矩形覆盖

输入描述:

输出描述:

输入

输出

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题