矩阵覆盖_铺地砖问题

描述：

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

思路：
 

target = 1大矩形为2*1，只有一种摆放方法，return1；
target = 2 大矩形为2*2，有两种摆放方法，return2；
target = n 分为两步考虑：
        第一次摆放一块 2*1 的小矩阵，则摆放方法总共为f(target - 1)

     第一次摆放一块1*2的小矩阵，则摆放方法总共为f(target-2)
因为，摆放了一块1*2的小矩阵（用√√表示），对应下方的1*2（用××表示）摆放方法就确定了，所以为f(targte-2)

1.递归

public int RectCover(int target) {
	      if(target  < 1){
	            return 0;
	        }
	        if(target == 1){
	            return 1;
	        }else if(target == 2){
	            return 2;
	        }else{
	            return RectCover((target-1))+RectCover(target-2);
	        }
	 
	    }

2.动态规划

public int RectCover(int target) {
		int[] dp=new int[target+1];
		dp[0]=0;	
		for (int i = 1; i <=target; i++) {
			if (i==1) dp[1]=1;
			else if (i==2) dp[2]=2;
			else dp[i]=dp[i-1]+dp[i-2];
		}
		return dp[target];
	}