[每日一道小算法（五）] [递归] 矩形的覆盖

港控/mmm° 2023-06-29 05:41 24阅读 0赞

前言：  
日常闲聊，哈哈，这道题是剑指offer上面的一道题，这道题很经典，看了代码你会觉得很简单，但是看这道题还是没有什么思路的，重要的是找思路，多举个例子测试一下，就会明白很多。好了不废话了，开撕，嗖 pa!!!

### 题目描述 ###

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

### 解题思路 ###

我们采用从能够简单到复杂的思路思考这个问题，当n=1的时候，只有一个2*1的矩形，所以只有一种方法，记为f(1)=1；当n=2的时候，是两个2*1的矩形，这时候具有两种方式去覆盖这个矩形了（这时候应该是一个正方形），一种是竖着放，一种是横着放，所以有两种方法，记为f(2)=2；

当n=3的时候，仍然只能采用横着放或者竖着放的方式去覆盖这个矩形，我们仍首先考虑使用竖着放的方式，当竖着放的时候，由于已经覆盖了左边（假设是从左边开始覆盖的，从右边的覆盖的效果是一样的）一个2*1的矩形，所以还有2个2*1的矩形，而这种情况我们已经在n=2的时候计算出来了，就是f(2)；接下来我们考虑横着放的情况，由于是横着放，在水平方向已经覆盖了一个2*1的矩形，所以要想覆盖这由3个2*1组成的矩形，只能在水平方向的覆盖的那个矩形下面继续覆盖一个，那么只剩下一个2\*1的矩形了，这也通过前面的分析计算出来了，就是f(1)。综合以上分析，当n=3的时候，覆盖的方法是f(3)=f(1)+f(2)。  
多试几次，还是这个规律，这不是跟斐波那契很像嘛，哈哈哈，找到解决办法了，于是代码如下。

### 代码样例 ###

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