剑指Offer（十）矩形覆盖（Java版 )

今天药忘吃喽~ 2021-09-26 22:28 250阅读 0赞

# 一、题目描述 #

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

# 二、题目分析 #

第一块有两种方式：横着放和竖着放  
横着放对应方法为f(n-2);  
竖着放下一步的放方法为f(n-1);  
所以总的放的方法为f(n)=f(n-1)+f(n-2);  
画一张图来描述下：  
![这里写图片描述][70]

# 三、方法一：递归 #

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);
        }
    }

运行结果：  
![这里写图片描述][70 1]

# 三、方法二：循环 #

public class Solution {
        public int RectCover(int target) {
            if( target == 0 ) return 0;
            if( target == 1 ) return 1;
            if( target == 2 ) return 2;
            int pre = 1;
            int now = 2;
            int result = 0;
            for( int i = 3;i <= target;i++ )
            {
                result = pre + now;
                pre = now;
                now = result;
            }
            return result;
        }
    }

运行结果：  
![这里写图片描述][70 2]

[70]: /images/20210923/97145b5581f04eb6af0b0f82c338c195.png
[70 1]: /images/20210923/02cabeb68cc94dcb82b85f8fa03829fe.png
[70 2]: /images/20210923/3a31d5a7bf86403b9de16c712a64da4d.png

发表评论取消回复

表情：

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

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

相关阅读

相关剑指offer 矩形覆盖

[剑指offer题型分类及各题的解题思路与代码（<---点我跳转 ^ - ^）][offer_---_ _ -] 1、题目描述我们可以用2\*1的小矩...

╰+哭是因爲堅強的太久メ/ 2024年04月18日 09:57/ 0 赞/ 63 阅读

相关剑指offer - 矩形覆盖

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

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

相关剑指Offer | 矩形覆盖

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

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

相关剑指Offer | 矩形覆盖

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

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

相关剑指offer：矩形覆盖

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

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

相关剑指offer矩形覆盖

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

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

相关剑指Offer-矩形覆盖

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

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

相关剑指offer-矩形覆盖

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

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

相关剑指Offer（十）矩形覆盖（Java版 )

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

今天药忘吃喽~/ 2021年09月26日 22:28/ 0 赞/ 251 阅读

相关剑指offer：矩形覆盖

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

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