题目
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
分析
这个题的比较难以下手，首先找一下规律，n=1，只有一种，n=2，是一个正方形，可以讲小矩形横着放或者竖着放：
当n=3，假如第三个小矩形恰好能够竖直放下，这个时候，就相当于只考虑第一个和第二个小矩形怎么放，也就是怎么用小矩形去填充一个正方形， 就回到了上一步，n=2时的方法，这个时候的方法数恰好就应该为f(2).
假如第三个小矩形恰好能够横着放下，这个时候第二个矩形也必定是横着放的，那么第二和第三个小矩形就确定了，只需要考虑第一个小矩形的摆放方法，也就是f(1).
那么f(3)=f(2)+f(1)。这个时候我们还不能完全看出规律。假如n很大的时候，我们只考虑n,n-1,n-2，这三个小矩形的摆放方式。如下图所示：
按照n=3 时候的思考，假如摆放第n个小矩形只能竖直摆放，那么恰好是下图这种情况：
这时，最后一个小矩形是固定的，只要考虑前面n-1个小矩形的摆放方法，就是f(n)。
接着，假如最后一个小矩形只能横着摆放，也就是下图所示：
这个时候，最后两个小矩形的位置固定的，就只需要考虑前n-2个小矩形的摆放方式，也就是f(2).
综上分析： f(n) = f(n-1) + f(n-2). (n >= 3)
f(2) = 2;
f(1) = 1
f(0) = 0;
代码
import javax.swing.text.html.parser.TagElement;
public class offer10 {
public static void main(String[] args) {
// TODO Auto-generated method stub
offer10 offer10 = new offer10();
System.out.println(offer10.RectCover(3));
}
public int RectCover(int target) {
if (target <= 0) {
return -1;
}
if (target == 1) {
return 1;
}
if (target == 2) {
return 2;
}
return RectCover(target -1) + RectCover(target-2);
}
}
