矩形覆盖

矩形覆盖

我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

n = 1 的时候
只能横着覆盖，一种
n = 2 的时候
可以横着和竖着覆盖，两种
n = 3 的时候
第三级横着覆盖，用了一级，剩下 n = 2，有两种覆盖方法
第三季竖着覆盖，用了两级，剩下 n = 1，有一种覆盖方法
总共有 3 种
n = 4 的时候
第 4 级横着覆盖，用了一级，剩下 n = 3，有三种覆盖方法
第 4 级竖着覆盖，用了两级，剩下 n = 2，有两种覆盖方法
总共有 5 种方法
n = n 的时候
第 n 级横着覆盖，用了一级，剩下 n = n - 1，所以关注第 n - 1 种有几种覆盖方法
第 n 级竖着覆盖，用了两级，剩下 n = n - 2，所以关注第 n - 2 种有几种覆盖方法
总和为两种情况的总和

public class RectangularCovering {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
        int result = RectCover(4);
		System.out.println(result);
	}

	public static int RectCover(int target) {
		if (target <= 2) {
			return target;
		}
		int pre1 = 2; // n 最后使用一块，剩下 n-1 块的写法
		int pre2 = 1; // n 最后使用两块，剩下 n-2 块的写法
		for (int i = 3; i <= target; i++) {
			int cur = pre1 + pre2;
			pre2 = pre1;
			pre1 = cur;
		}
		return pre1; // 相对于 n+1 块来说，第 n 种的方法
	}
}