矩形覆盖
题目描述
10、我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
解题思路：
1）、当 n = 1时，矩阵大小n = 2时，为2*1时，只有1种覆盖方法，即f(1) = 1；
2）、当 n = 2时，矩阵大小为2*2时，有2种覆盖方法，即f(2) = 2；
3）、当 n = 3时，矩阵大小为2*3时，有3种覆盖方法，即f(3) = 3；
4）、当然我们没必要一个个去列举所有的，直接假设有n个大小的2*1矩阵，即2*n矩阵进行考虑方法。
当第一次覆盖2*1的小矩阵（竖着放），则后面的覆盖方法为f(n-1);
当第一次覆盖1*2的小矩阵（横着放），对应下方的1*2的小矩阵摆放必然是确定的，所以后面的覆盖方法为f(n-2)。
所以总的覆盖方法为：f(n) = f(n-1) + f(n-2); 依旧是斐波那契数列的算法。
class Solution {
public:
int rectCover(int number) {
// 斐波那契 2017-6-18
if(number==1) return 1;
if(number==0) return 0;
if(number==2) return 2;
number-=2;
int f=1;
int s=2;
while(number--)
{
s=s+f;
f=s-f;
}
return s;
}
};
public:
int rectCover(int number) {
// 斐波那契 2017-6-18
if(number==1) return 1;
if(number==0) return 0;
if(number==2) return 2;
number-=2;
int f=1;
int s=2;
while(number--)
{
s=s+f;
f=s-f;
}
return s;
}
};