剑指Offer | 矩形覆盖

左手的ㄟ右手 2022-05-25 14:07 141阅读 0赞

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

## 一、题目 ##

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

## 二、思路 ##

依旧是斐波那契数列。  
用归纳法归纳如下，  
（1）当 n < 1时，显然不需要用2\*1块覆盖，按照题目提示应该返回 0。  
（2）当 n = 1时，只存在一种情况。  
![这里写图片描述][70]  
（3）当 n = 2时，存在两种情况。  
![这里写图片描述][70 1]  
（4）当 n = 3时，明显感觉到如果没有章法，思维难度比之前提升挺多的。  
![这里写图片描述][70 2]  
… 尝试归纳，本质上 n 覆盖方法种类都是对 n - 1 时的扩展。  
可以明确，n 时必定有 n-1时原来方式与2\*1的方块结合。也就是说, f(n) = f(n-1) + ?(暂时无法判断)。  
（4）如果我们现在归纳 n = 4，应该是什么形式？  
4.1）保持原来n = 3时内容，并扩展一个 2\*1 方块，形式分别为 “| | | |”、“= | |”、“| = |”  
4.2）新增加的2\*1 方块与临近的2\*1方块组成 2\*2结构，然后可以变形成 “=”。于是 n = 4在原来n = 3基础上增加了”| | =”、“= =”。  
再自己看看这多出来的两种形式，是不是只比n = 2多了“=”。其实这就是关键点所在…因为，只要2\*1或1\*2有相同的两个时，就会组成2\*2形式，于是就又可以变形了。  
所以，自然而然可以得出规律： f(n) = f(n-1) + f(n-2)， (n > 2)。

## 三、代码 ##

public class Solution {
        public int RectCover(int target) {
            if (target < 1) {
                return 0;
            } else if (target == 1 || target == 2) {
                return target;
            } else {
                return RectCover(target-1) + RectCover(target-2);
            }
        }
    }

[https_blog.csdn.net_mengmengdastyle_article_details_80317246]: https://blog.csdn.net/mengmengdastyle/article/details/80317246
[70]: /images/20220525/9e223731aa124694918c86032d3fc4f6.png
[70 1]: /images/20220525/45b39d56a88741fa8f2cec208b553e94.png
[70 2]: /images/20220525/612b7cd433154b1293824f52a0711d7d.png