Sword to Offer-10.2 矩形覆盖 ❀
in Algorithm
题目描述：我们可以用
2 * 1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2 * 1的小矩形无重叠地覆盖一个2 * n的大矩形，总共有多少种方法？比如
n = 3时，2 * 3的矩形块有3种覆盖方法：
解题思路：
1、关键在于理解为什么这是斐波那契问题；
2、当n=1时，只有一种摆放方法，当n=2时，有两种摆放方法；
3、当n=3时，
（1）假设第一块竖放，那么接下来是一个n=2摆放问题，已知有两种摆放方法；
（2）假设第一块横放，那么其下面那块区域必须同样横放一个2*n的矩阵，这是第一块横放情况下确定的，所以接下来是一个n=1摆放问题，已知有一种摆放方法；
（3）第一块横放或者竖放已经包含了第一块所有可能的摆放方式，因而f(3)=f(2)+f(1);
4、当n>3时，情况也如此，f(n)=f(n-1)+f(n-2)。
问题图解：
AC代码：
// Cover a 2*n Rectangle with 2*1 Rectangle
public class Solution {
public int RectCover(int target) {
if (target <= 1) {
return target;
}
int[] method = new int[target+1];
method[1] = 1;
method[2] = 2;
for (int i=3; i<=target; i++) {
method[i] = method[i-1] + method[i-2];
}
return method[target];
}
}
