剑指offer面试题[9-3]-矩形覆盖

绝地灬酷狼 2022-06-13 02:23 162阅读 0赞

## 题目描述 ##

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

分析：

(1) n等于1时，总共有1种方法。

(2) n等于2时，总共有2种方法。

2\*1的矩形，横着或竖着分别一种。

(3) n等于3时，总共有3种方法。

1) 2\*1的矩形全部竖着放;  2)第一列 2\*1的矩形竖着放，后面两列横着放两个2\*1的矩形; 3)前面两行横着放两个2\*1的矩形，最后一列竖着放一个2\*1的矩形。

.............................

我们可以看到，由于 2\*1的小矩形可以横着放也可以竖着放，当n=3的时候，在n=2的基础上其实只有一种放法了，就是把第三个 2\*1的小矩形竖着放，在n=1的基础上，把第二个和第三个2\*1的小矩形横着放（有人会说为什么竖着放两个不算，这已经包括在n=2的情况下了）。所以抽象表示就是f(3)=f(2)+f(1)。也还是裴波那契的思想。不过如果用递归复杂度比较高，因此我们还是用“跳台阶”的方法来实现。

程序如下：

class Solution \{  
public:  
    int rectCover(int number) \{   
         int result\[3\]=\{0,1,2\};  
         if(number<3)  
             return result\[number\];  
         int frontRectar1=1;                         //矩形rectar  
         int frontRectar2=2;  
         int sumRectar;  
         for(int i=3;i<=number;i++)  
           \{   
              sumRectar=frontRectar1+frontRectar2;  
              frontRectar1=frontRectar2;  
              frontRectar2=sumRectar;  
           \}  
         return sumRectar;  
    \}  
\};