一、题目描述
我们可以用2x1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2x1的小矩形无重叠地覆盖一个2xn的大矩形，总共有多少种方法？
二、算法分析
如果是1x2的，只有一种覆盖方法，如果是2x2的，则有两种，2xn的矩形由前两种组合而成
定义f(n)表示2xn的矩阵的覆盖法，那么如同前面的跳台阶一样，只有两种可能，最后剩下的是1x2的矩形或则是2*2的矩形，所以f(n)=f(n-1)+f(n-2)
此处还是采用记事本法，记录每一种的覆盖数数，避免重复计算，
三、算法实现
public class Solution {
int[] log = new int[1000];
public int RectCover(int target) {
int n = target;
if(n==0|n==1||n==2)
return n;
if(log[n]==0)
log[n]=RectCover(n-1)+RectCover(n-2);
return log[n];
}
}
文章为个人编辑，如有错误，欢迎指正！
网友评论