剑指offer【面试题10 ：矩形覆盖】

题目：

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

思路1：假设某方案中用了a个横着的小矩形、b个竖着的小矩形

那么，n = 2*a + 1*b；可以编程求出所有的a与b；例如：n = 4的时候；解为：

a = 0, b = 4;

a = 1, b = 2;

a = 2, b = 0;

有三组解，剩下的问题，正对一个解，都是一个排列组合问题，暂时没搞懂；

思路2：

如图：你知道当我们遍历一个长度为n（宽度当然是2啦）的矩形的时候；要么竖着放一个，要么横着放，只要横着放，那么下面一定也只能横着放一块（如图横着放的红色下面一定只能再横着放一块，如图黄色块）。

所以，当我们执行循环的时候（设每一种当前矩形的列的累加值为m，保存在vector<int>sums中），每次都有m “+1” 和m “+2” 两种可能；我们每一个循环统计出 m = number的个数；直到 sums中的每一个m都大于 number；

  1 //我们可以用2 * 1的小矩形横着或者竖着去覆盖更大的矩形。
  2 //请问用n个2 * 1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
  3 // 思路： 
  4 // n = 1*a + 2*b
  5 // 我们求解出来a、b,然后在求特定的排列组合
  6 #include<iostream>
  7 #include<list>
  8 #include<algorithm>
  9 #include<list>
 10 #include<vector>
 11 #include<boost/timer.hpp>
 12 using namespace std;
 13 
 14 void PrintVector(const list<int>& vec_)
 15 {
 16     for (auto& element_:vec_)
 17     {
 18         cout.width(3);
 19         cout << element_ << " ";
 20     }
 21     cout << endl;
 22 }
 23 
 24 //容器每个元素都 大于 number
 25 bool IsBigger( const list<int>& vec, int number)
 26 {
 27     for (auto& element_:vec)
 28     {
 29         if (element_ > number)
 30             continue;
 31         else
 32             return false;
 33     }
 34     return true;
 35 }
 36 
 37 int rectCover(int number) // 9
 38 {
 39     if ((number == 1) || (number == 2))
 40     {
 41         return number;
 42     }
 43     else // number >= 3
 44     {
 45         bool isbigger = false;
 46         list<int> sums;
 47         int count = 0;
 48         sums.push_back(1);
 49         sums.push_back(2);
 50         int i, j;
 51         for (int i = 1;; i++)
 52         {
 53             int sizeofsums = 2*sums.size(); // 2 4 8 16 32指数增长
 54             vector<int> temp;
 55             list<int>::iterator itr = sums.begin();
 56             //将当前sums中所有元素+1；并且将sums的size扩大一倍
 57             // 例如：sizeofsums = 8时
 58             for ( int n = 0; n <sizeofsums; n++)
 59             {
 60                 // 
 61                 if (n < (sizeofsums / 2))
 62                 {
 63                     (*itr) += 1;// sums[0]、sums[1] 、sums[2] 、sums[3]自增1 
 64                     temp.push_back(*itr);
 65                     itr++;//只能在这里
 66                 }
 67                 else
 68                 {
 69                     //sums[4]、sums[5] 、sums[6] 、sums[7]自增1（实际是+2）
 70                     sums.push_back(temp[n - (sizeofsums / 2)] + 1);// push_back让容器自动扩容；
 71                 }
 72                 
 73             }
 74             //PrintVector(sums);
 75             // 计算当前符合条件的方案数量
 76             for (auto& ele_ : sums)
 77             {
 78                 if (ele_ == number)
 79                 {
 80                     count++;
 81                 }
 82             }
 83             // 删除溢出的方案
 84             for (list<int>::iterator itr = sums.begin(); itr != sums.end();)
 85             {
 86                 if (*itr >= number)
 87                 {
 88                     itr = sums.erase(itr);
 89                 }
 90                 else
 91                 {
 92                     itr++;
 93                 }
 94             }
 95             //cout << "删除后" << endl;
 96             //PrintVector(sums);
 97             if (IsBigger(sums, number)) //如果每一个元素都大于 number；那么list<int> sums的解就被收集干净了
 98                 break;
 99         }
100         return count;
101     }
102 }
103 int main()
104 {
105     boost::timer timer1;
106     cout << "ways = " << rectCover(29) << endl;//5
107     cout << "cost of  time is :" << timer1.elapsed() << endl;
108     cout << "ways = " << rectCover(5) << endl;//5
109     cout << "ways = " << rectCover(4) << endl;//5
110     cout << "ways = " << rectCover(3) << endl;//5
111     cout << "ways = " << rectCover(2) << endl;//5
112     cout << "ways = " << rectCover(1) << endl;//5
113     return 1;
114 }