【剑指Offer题解：java】矩形覆盖

忘是亡心i 2023-01-10 09:57 105阅读 0赞

### 文章目录 ###

*   *  题目
     *  分析
     *  代码

## 题目 ##

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

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

![8428a44fe18091490f4ce46ee04ae603.png][]

> 看完题目的我一脸懵，对题目进行分析

## 分析 ##

**n = 1时，显然只有一种情况**

![image.png][]

**n =2时显然2种情况**

![image.png][image.png 1]

**n=3时3种情况**

![8428a44fe18091490f4ce46ee04ae603.png][]

**n = 4时5种情况**

![image.png][image.png 2]

从n=3到n=4，怎么来的呢？

这里有2种情况：

*  直接在n=3的情况下，再后面中添加一个竖着的。这个很显然成立，有3种情况
 *  然后横着的显然能添加到n-2的情况上，也就是在n=2后面，添加2个横着的。有2种情况

**规律**：

所以总结：f \[n\]表示2\*n大矩阵 的方法数。

可以得出：f\[n\] = f\[n-1\] + f\[n-2\]，初始条件f\[1\] = 1, f\[2\] =2

> 这不是传说中的斐波拉契数列吗？

所以代码可用递归，记忆递归，和动态规划和递推

[其他方法参考斐波拉契数列][Link 1]

## 代码 ##

public int rectCover(int n) { 
           if (n==0 || n==1 || n==2) return n;
           int a = 1, b = 2, c = 0;
           for (int i=3; i<=n; ++i) { 
              c = a + b;
              a = b;
              b = c;
            }
           return c;
        }

[8428a44fe18091490f4ce46ee04ae603.png]: /images/20221119/93d50570ee6746d5a138ebbebe3c0e4c.png
[image.png]: /images/20221119/ee5ec02391e949ae91adc307bb546576.png
[image.png 1]: /images/20221119/515a7485444a4e6fbc3cf1ef35c9e6ab.png
[image.png 2]: /images/20221119/4839eb5a93a449b481cc082083f21cde.png
[Link 1]: https://youkaiyang.blog.csdn.net/article/details/112927202

发表评论取消回复

表情：

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

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

相关阅读

相关 10 图解剑指Offer 矩形覆盖 Java题解

10 图解剑指Offer 矩形覆盖 Java题解 10 图解剑指Offer 矩形覆盖 Java题解题目链接题目描述

野性酷女/ 2023年02月20日 08:23/ 0 赞/ 8 阅读

相关【剑指Offer题解：java】矩形覆盖

文章目录题目分析代码题目我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一

忘是亡心i/ 2023年01月10日 09:57/ 0 赞/ 106 阅读

相关剑指offer - 矩形覆盖

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

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

相关剑指Offer | 矩形覆盖

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

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

相关剑指Offer | 矩形覆盖

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

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

相关剑指offer：矩形覆盖

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

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

相关剑指offer矩形覆盖

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

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

相关剑指Offer-矩形覆盖

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

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

相关剑指offer-矩形覆盖

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

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

相关剑指offer：矩形覆盖

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

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