原题链接
描述
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，从同一个方向看总共有多少种不同的方法？
示例
输入：4
返回值：5
思路
从头开始递推，2*1 只有一种，2*2有两种（全横向或者全纵向），2*3有3种，这样很容易总结出：2*n的大矩形的覆盖方法是2*(n-1) 和2*(n-2)的覆盖方法数之和。
解答
public class Solution {
public int rectCover(int target) {
if (target <= 2) return target;
int res = 0;
int pre1 = 1, pre2 = 2;
for (int i = 3; i <= target; i++) {
res = pre1 + pre2;
pre1 = pre2;
pre2 = res;
}
return res;
}
}