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

题目描述

我们可以用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;

    }

};