《剑指Offer》Java刷题 NO.10 矩形覆盖
《剑指Offer》Java刷题 NO.10 矩形覆盖(斐波那契数列)
时间：2020-02-12 题目： 我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
思路： 又是斐波那契数列的一个应用 把长边(n)看成n级，每个单位为一级，突破点在于最后一个矩形的覆盖方式 初始条件： n=1时，1种方式 n=2时，2种方式
Java代码：
/**
* 我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。
* 请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
*/
public class RectCover {
public int rectCoverWays(int n){
if(n==0) return 0;
else if(n==1) return 1;
else if(n==2) return 2;
int sum=2;
int f1=1;
for(int i=3;i<=n;i++) {
sum=sum+f1;
f1=sum-f1;
}
return sum;
}
}
