java实现矩形覆盖(思路与实现)
题目描述
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？ 我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
思路：
其实这道题也是一个斐波那契数列的一个应用
1、当target <= 0, 说明没有矩形，所以return 0；
2、当target == 1, 则大矩形是一个2*1，小矩形也是一个2*1，此时return 1；
3、当target == 2，则大矩形是一个2*2，小矩形则是两个2*1，此时return 2（为什么要返回，是因为这个最小的单位其实就是target == 1 和target ==2的时候）；
4、当target > 2, 这个时候就需要分开讨论。
然后咱们把放矩形细化为第一步：
当第一步摆放一个2*1（竖着放）的小矩型的时候，后面还有target-1个位置可以未知的摆放小矩形。所以细化后变成（target - 1）的问题；
当第一步摆放一个1*2*（横着放）的小矩形的时候，下面的这个小矩形的空位已经定死了，所以只能横着放一个小矩形，这个时候后面就只能由target-2个位置可以未知的摆放小矩形，所以细化后变成（target-2）的问题；
实现：
public int RectCover(int target) {
if(target <= 0){
return 0;
}else if(target == 1){
return 1;
}else if(target == 2){
return 2;
}else{
return RectCover(target - 1) + RectCover(target - 2);
}
}
