剑指offer--矩形覆盖（斐波那契）

迈不过友情╰ 2023-02-14 10:47 24阅读 0赞

## 题目描述 ##

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

比如n=3时，`2*3`的矩形块有3种覆盖方法：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczMDUwOA_size_16_color_FFFFFF_t_70]

## 解决方法 ##

刚看到题就懵了！一个个画出来，找规律  
![在这里插入图片描述][20200602163908284.png]  
![在这里插入图片描述][20200602163927478.png]  
![在这里插入图片描述][20200602163953250.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczMDUwOA_size_16_color_FFFFFF_t_70 1]  
`找规律题，用到递归、循环`

被覆盖的目标矩形的形状： 2\*n  
每次新增加的：  
（1）如果竖着放对应的情况与 target为 n-1 时相同；  
（2）如果横着放，对应的情况与 target 为 n-2 时相同。

## 递归 ##

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

## 递推 ##

需要`注意target=0`的情况，和`跳台阶`要区分开

public class Solution {
        
        public int RectCover(int target) {
        
            if(target<=2)
                return target;
            int a=1,b=2;
            for(int i=3;i<=target;i++){
        
                b=a+b;
                a=b-a;
            }
            return b;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczMDUwOA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200602163003647.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczMDUwOA==,size_16,color_FFFFFF,t_70
[20200602163908284.png]: https://img-blog.csdnimg.cn/20200602163908284.png
[20200602163927478.png]: https://img-blog.csdnimg.cn/20200602163927478.png
[20200602163953250.png]: https://img-blog.csdnimg.cn/20200602163953250.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczMDUwOA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200602164048948.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczMDUwOA==,size_16,color_FFFFFF,t_70