首页 > 试题广场 >

矩形覆盖

[编程题]矩形覆盖
  • 热度指数：611507 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
我们可以用 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)
Java
牛客151616704号头像 牛客151616704号

小矩形无非两种摆法，横着摆或竖着摆。

定义 F(n)，含义为在 2 * n 的区域里摆满小矩形，有几种方法？

① 第一种选择：小矩形竖着摆，就变成了 2 * (n - 1) 列的区域 --> F(n - 1)。

② 第二种选择：小矩形横着摆，下面的位置的小矩形也必须横着摆，变成了 2 * (n - 2) 列的区域 --> F(n - 2)。

因此 F(n) = F(n - 1) + F(n - 2)，斐波那契数列问题，严格递推。

矩阵快速幂，时间复杂度 O(logN)： 
import java.util.*;
public class Solution {
    public int rectCover(int target) {
        if(target < 1) {
            return 0;
        }
        if(target == 1 || target == 2) {
            return target;
        }
        int[][] base = {{1, 1}, {1, 0}};
        int[][] res = matrixPower(base, target - 2);
        return 2 * res[0][0] + res[1][0];
    }

    public int[][] matrixPower(int[][] m, int p) {
        int[][] res = new int[m.length][m[0].length];
        for(int i = 0; i < res.length; i++) {
            res[i][i] = 1;
        }
        int[][] t = m;
        for(; p != 0; p >>= 1) {
            if((p & 1) != 0) {
                res = multiMatrix(res, t);
            }
            t = multiMatrix(t, t);
        }
        return res;
    }

    public int[][] multiMatrix(int[][] m1, int[][] m2) {
        int[][] res = new int[m1.length][m2[0].length];
        for(int i = 0; i < m1.length; i++) {
            for(int j = 0; j < m2[0].length; j++) {
                for(int k = 0; k < m2.length; k++) {
                    res[i][j] += m1[i][k] * m2[k][j];
                }
            }
        }
        return res;
    }
}



发表于 2023-06-18 16:09:02 回复(0)
Java
ludvig头像 ludvig 
//变相的跳台阶问题 重点在于理解这个矩形拼凑的关系 找到转移方程
//2*n大小矩阵最后结尾的那个矩形要么是一个竖的 要么是两个横的 
//2*n大小的矩阵 要么是2*(n-1)大小的矩阵竖着拼一个2*1的 要么是2*(n-2)大小的矩阵横着拼两个1*2的 
public class Solution {
    public int rectCover(int target) {
        if(target==0){
            return 0;
        }
        if(target<=2){
            return target;
        }
        int[] dp = new int[target];
        dp[0] = 1;
        dp[1] = 2;
        for (int i = 2; i < dp.length; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[dp.length-1];
    }
}

发表于 2022-11-10 10:31:17 回复(0)
Java
必进大厂的飞头像 必进大厂的飞 
    /**
     * 矩形覆盖
     * 状态转移方程：             dp[i] = dp[i-1] + dp[i-2];
     * 本质上和上楼梯是一样的 要么一次一格要么一次两格
     * @param target
     * @return
     */
    public int rectCover(int target) {
        int[] dp = new int[target + 1];
        //base case
        if(target >= 1) dp[1] = 1; if(target >=2) dp[2] = 2;
        for(int i = 3; i<= target; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[target];
    }

发表于 2022-05-01 14:10:38 回复(0)
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)
Java
xiaojiangshi头像 xiaojiangshi 
public class Solution {
    public int rectCover(int target) {
        if(target == 0){
            return 0;
        } else if(target == 1){
            return 1;
        } else if(target == 2){
            return 2;
        }
        
        int a = 1;
        int b = 2;
        
        for(int i = 3; i <= target; i++){
            int temp = a + b;
            a = b;
            b = temp;
        }
        
        return b;
    }
}
 
根据官方画的示例图，可以发现，当n = 3时，是在n = 2的右边添加一个矩形，并没有考虑左边添加矩形；也是在n = 1的右边添加矩形，且都形成唯一矩形。所以这题的理解就是：只需要在n-1和n-2所展示的矩形的右边添加新的或1或2个矩形。
发表于 2022-04-09 10:45:44 回复(0)
Java
Shrink9头像 Shrink9
/**
* 直接交表
*/
public class Solution {
    public int rectCover(int target) {
        int[] res={0,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986};
        return res[target];
    }
}
发表于 2022-03-16 11:52:22 回复(1)
Java
牛客989812257号头像 牛客989812257号 
public class Solution {
    public int rectCover(int target) {
        if(target<=2){
            return target;
        }
        return rectCover(target-1)+rectCover(target-2);
    }
}

发表于 2022-02-14 20:32:53 回复(0)
Java
浮鸟(BAT实习ing，目标外企~)头像 浮鸟(BAT实习ing，目标外企~) 
public class Solution {
    public int rectCover(int target) {
        // 递推，可转化为斐波那契数列
        // f(n)=f(n-1)+f(n-2)
        int a=0;
        int b=1;
        int sum = 0;
        for(int i=0;i<target;i++){
            sum = a+b;
            a = b;
            b = sum;
        }
        return sum;
    }
}

发表于 2022-01-16 22:17:03 回复(0)
Java
是小王吖🐅头像 是小王吖🐅 
public class Solution {
    private int rst=0;
    public int rectCover(int target) {
        if(target==0) return 0;
        dfs(target,1);
        dfs(target,2);
        return rst;
    }
    public void dfs(int target,int width){
        if(target==width)
            rst++;
        else if(target<width)
            return;
        else{
            dfs(target-width,1);
            dfs(target-width,2);
        }
    }
}

发表于 2022-01-16 09:06:19 回复(0)
Java
我不打朋友圈头像 我不打朋友圈 
//当n>2时，考虑第n块的放置方式，横着放或者是竖着放
//竖着放的时候有f（n-1）种，
//横着放的时候有f（n-2）种
public class Solution {
    public int rectCover(int target) {
        return f(target);

    }
    public int f(int n){
        if(n < 1) return 0;
        if(n == 1) return 1;
        if(n == 2) return 2;
        return f(n-1) + f(n-2);
    }
}

发表于 2021-12-31 13:05:18 回复(0)
Java
再也不玩刮刮乐头像 再也不玩刮刮乐 
 public int rectCover(int target) {
        if(target<3) return target;
        return rectCover(target-1)+rectCover(target-2);
    }

发表于 2021-09-09 16:44:17 回复(0)
Java
牛客905282397号头像 牛客905282397号
和跳格子类似 
public class Solution {
    public int rectCover(int target) {
        int a= 2; int b=1;
        if(target==0||target==1 || target==2) return target;
        for(int i = 3; i<=target;i++){
            a=a+b;
            b=a-b;
        }
        return a;
    }
}
时间复杂度O(n), 空间复杂度O(1)

发表于 2021-06-24 13:54:49 回复(0)
Java
雄滚滚头像 雄滚滚 
//同上面
public class Solution {
    public int rectCover(int target) {
        if(target==0||target==1||target==2){
            return target;
        }
        int a=1,b=2,c=0;
        for(int i=3;i<=target;i++){
            c= a+b;
            a=b;
            b=c;
        }
        return c;
    }
}

发表于 2021-05-10 21:07:26 回复(0)
Java
阿尼亚瓦库瓦库头像 阿尼亚瓦库瓦库
其实这个和跳台阶是一个类型的问题啦~~~~ 
public class Solution {
    public int rectCover(int target) {
        if (target == 0) {
            return 0;
        }

        return getResult(target);
    }

    private int getResult(int target) {
        if (target == 0) {
            return 1;
        }

        if (target == 1) {
            return 1;
        }

        return getResult(target - 1) + getResult(target - 2);
    }
}
动态规划法： 
public class Solution {
    public int rectCover(int target) {
        if (target == 0 || target == 1) {
            return target;
        }

        return getResult(target);
    }

    // 动态规划解法：
    private int getResult(int target) {
        int[] dp = new int[target + 1];

        dp[0] = 1; //这里是为了方便才设为1
        dp[1] = 1;

        for (int i = 2; i <= target; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[target];
    }
}



编辑于 2021-05-01 17:02:57 回复(0)
Java
624huiguorou头像 624huiguorou
/*
    思路：
    为斐波那契数列
    
    注意：
    当target为0时，结果应该是0种方法
    
    斐波那契数列思路：
    斐波那契数列 固定思路
    
    1.使用递归 不是最好方法
    2.递推 是最好方法 时间复杂度O(n) 空间复杂度O(1)
    用a和b变量来作为中间变量
    使用a+b来得到下一个数然后不断覆盖a和b
    a保存每次的结果
*/ 
    public int rectCover(int target) {
        if(target < 0) return -999;
        if(target == 0) return 0;
        int a = 1,b = 2;
        for(int i = 1;i < target;i++){
            int temp = a + b;
            a = b;
            b = temp;
        }
        return a;
    }


发表于 2021-04-07 21:48:27 回复(0)
Java
酸辣毛小豆头像 酸辣毛小豆 
public class Solution {
    public int rectCover(int target) {
        if(target==0)
            return 0;
        if(target==1||target==2)
            return target;
        int a = 2,b = 1;
        for(int i = 3;i <=target;i++){
            a = a + b;
            b = a - b;
        }
        return a;
    }
}
自顶向上。起始我觉得这题出得不是很严谨，当n == 2的时候，横着放和竖着放应该算作一个，不能算作两个
发表于 2021-03-21 16:26:20 回复(0)
Java
路平头像 路平 
/**
本题思路：分析小方块组合可能
矩形所有情况都包括在这两种可能里：以一块竖块或是两块横块结尾
观察可发现：2*（n-2）的情况下在结尾添加两个横块 或2*（n-1）的情况下结尾添加一个竖块即可满足2*n的所有情况
所有则有 f（n) = f(n-1) + f(n-2)
即斐波那契数列
*/
public class Solution {
    public int rectCover(int target) {
        int[] res = new int[]{0,1,2};
        if (target < 3) {
            return res[target];
        }
        for (int i = 3; i<=target; ++i) {
            res[0] = res[2];
            res[2] = res[1] + res[2];
            res[1] = res[0];
        }
        return res[2];
    }
}

发表于 2021-02-05 10:42:23 回复(0)
Java
匿迹小王子头像 匿迹小王子 
    /**
     * 解题思路：
     *
     * 动态规划。x(target) = x(target-1) + x(target-2)
     *
     * @author freedom wang
     * @date 2021-01-23 10:48:08
     */
    public int rectCover(int target) {
        if (target == 0 || target == 1) {
            return target;
        }

        int[] array = new int[target + 1];
        array[0]= 1;
        array[1]= 1;

        for (int i = 2; i < target + 1; i++) {
            array[i] = array[i-1] + array[i-2];
        }

        return array[target];
    }
编辑于 2021-01-23 10:52:45 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

矩形覆盖

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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