题目描述

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？   使用dp，当n时，选着竖着放一个，那么后面的可能性为f(n-1) 　　　　　　　 选择横着放一个，那么要占两个位置，后面的可能性为f(n-2) 故f(n)=f(n-1)+f(n-2)，f(1)=1，f(2)=2, (斐波那契数列) 
 1 public int RectCover(int target) {
 2         if(2>=target){
 3             return target;
 4         }
 5         int x1 = 1;
 6         int x2= 2;
 7         int re = 0;
 8         for(int i=3;i<=target;i++){
 9             re = x1+x2;
10             x1 = x2;
11             x2 = re;
12         }
13         return re;
14     }

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。