题目描述
我们可以用2乘1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2乘1的小矩形无重叠地覆盖一个2乘n的大矩形，总共有多少种方法？
思路分析
1）先考虑特殊情况，当 n < 1时，显然是不能满足，那么只能返回 0 ；
2）当 n = 1 时，只能有一种情况；
image.png
3）当 n = 2 时，有两种情况；
1
2
4）当 n = 3 时，如下；
3
5）继续归纳，当 n = 4，也就是在 4）步骤的基础上，多加两种情况。
5
归纳总结规律，f(1) = 1; f(2) = 2; f(3) = f(1) + f(2) = 3;
f(4) = f(3) + f(2) = 5;....f(n) = f(n-1) +f(n-2) (n>2)。
代码如下：
public class Solution {
public int RectCover(int target) {
if (target < 1) {
return 0;
} else if (target == 1 || target == 2) {
return target;
} else {
return RectCover(target-1) + RectCover(target-2);
}
}
}
参考文献：https://www.nowcoder.com/questionTerminal/72a5a919508a4251859fb2cfb987a0e6
