题目:我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?
public class Solution {
public int RectCover(int target) {
if(target <= 2){
return target;
}
return RectCover(target - 1) + RectCover(target - 2);
}
}
我们只关注最后面的一个矩形是横着放还是竖着放,就可以了,如果是竖着放的,其对应的方法数为n-1个矩形的方法,如果是横着放的,其对应的方法数为n-2个矩形的方法数,n个矩形的方法数为,前面两项的和,所以这又是一个斐波那契问题,仍可以用递归和迭代的方法去实现。