日常刷题之剑指offer：10.2.矩形覆盖

妖狐艹你老母 2022-12-02 13:56 100阅读 0赞

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

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NoT0xn_size_16_color_FFFFFF_t_70_pic_center]

# 二、解题思路 #

## 1.此题同样是考斐波那契数列，有一点点不同 ##

![在这里插入图片描述][20200831150424793.png_pic_center]

## 2.同样可以使用递归和动态规划实现：下面只给出动态规划的代码实现 ##

public class Solution { 
        public int RectCover(int target) { 
            if(target <= 2) return target;
            int[] dp = new int[target + 1];
            dp[0] = 0;
            dp[1] = 1;
            dp[2] = 2;
            for(int i = 3; i <=target; i++) { 
                dp[i] = dp[i-1] + dp[i-2];
            }
            return dp[target];
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NoT0xn_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/d26b6fd6b595416aaba601f5faee8f45.png
[20200831150424793.png_pic_center]: /images/20221123/08d29dbd202a46aaa6512a1ca22b3947.png

发表评论取消回复

表情：

评论列表（有 0 条评论，100人围观）

还没有评论，来说两句吧...

相关阅读

相关日常刷题之剑指offer：10.2.矩形覆盖

一、问题描述：我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2\n的大矩形，总共有多少种方法？比如n=3时，2\3的矩形块

妖狐艹你老母/ 2022年12月02日 13:56/ 0 赞/ 101 阅读

相关剑指offer - 矩形覆盖

public class Solution { public int RectCover(int target) { int [

谁借莪１个温暖的怀抱￠/ 2022年09月25日 01:27/ 0 赞/ 159 阅读

相关剑指Offer | 矩形覆盖

做了个剑指Offer的题目目录，链接如下： [https://blog.csdn.net/mengmengdastyle/article/details/80317246]

左手的ㄟ右手/ 2022年05月25日 14:07/ 0 赞/ 174 阅读

相关剑指Offer | 矩形覆盖

做了个剑指Offer的题目目录，链接如下： [https://blog.csdn.net/mengmengdastyle/article/details/80317246]

曾经终败给现在/ 2022年05月24日 00:23/ 0 赞/ 194 阅读

相关剑指offer：矩形覆盖

题目描述我们可以用2\1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2\1的小矩形无重叠地覆盖一个2\n的大矩形，总共有多少种方法？链接：[https://ww

绝地灬酷狼/ 2022年04月14日 05:13/ 0 赞/ 228 阅读

相关剑指offer矩形覆盖

原题目链接：[剑指offer矩形覆盖][offer] -------------------- 分类剑指offer 递归 ------------------

忘是亡心i/ 2022年04月13日 15:20/ 0 赞/ 241 阅读

相关剑指Offer-矩形覆盖

题目描述我们可以用2×1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2×1的小矩形无重叠地覆盖一个2×n的大矩形，总共有多少种方法？解题思路：n=1时，有1种方

骑猪看日落/ 2022年03月01日 08:38/ 0 赞/ 246 阅读

相关剑指offer-矩形覆盖

题目描述我们可以用2\ 1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2\ 1的小矩形无重叠地覆盖一个2\ n的大矩形，总共有多少种方法？实现思想依旧是

﹏ヽ暗。殇╰゛Y/ 2022年02月16日 10:58/ 0 赞/ 267 阅读

相关 JavaScript版《剑指offer》刷题（9）矩形覆盖

1.题目描述我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2\n的大矩形，总共有多少种方法？ 2.题目分析 1.先上图：

朱雀/ 2022年01月17日 04:05/ 0 赞/ 195 阅读

相关剑指offer：矩形覆盖

试题：我们可以用2\1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2\1的小矩形无重叠地覆盖一个2\n的大矩形，总共有多少种方法？代码：同样是总结出规律，然后使

冷不防/ 2021年06月24日 16:00/ 0 赞/ 484 阅读