最近一直在复习一些算法及数据结构方面的东西，就找了一个适合找工作笔试的题目，在剑指Offer上刷了几道题目，发现对复习知识点还是很有用的，做到重建二叉树这块。递归传值出了点问题，debug半小时才找出错误，所有还是写篇博客记录一下。也推荐要找工作的伙伴去剑指Offer刷题。
题目描述
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
一看这个题目可以发现，用2*1的小矩阵去横着或者竖着覆盖大矩形，可以分为两种情况：
1. 竖着放：
可以看出2个2*1的矩阵就是一个组合，很容易发现递归关系式，就是 target = recusion(target - 2)，第n项和第n-1项是不可分开的;
2. 横着放：
这一看就跟清楚了，target = recusion(target - 1); 具有最有子结构的特点。
如下代码递归式:
public int RectCover(int target) {
if(target 0){
return target;
}else if(target >= 3){
return RectCover(target - 1) + RectCover(target - 2);
}
return 0;
}
可以看到耗时还是挺慢的，其实递归在数据很大的情况下，很容易导致栈溢出。不仅执行时间慢，而且还会计算重复的步骤，下面是一个优化的版本：
记忆化的DP: 避免了递归重复计算的问题，但是增加了空间复杂度
static int[] arrs = new int[1000];
public static int RectCover(int target) {
if(target 时间快了不少。
这个递归其实跟斐波拉切数列是一样的，我们可以用3个整形变量来存放递归重复算的结果,如下：
public static int RectCover(int target) {
if(target 0){
return target;
}else{
int first = 1;
int second = 2;
int result = 0;
for(int i = 3 ; i 
来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/2971/viewspace-2813202/ ，如需转载，请注明出处，否则将追究法律责任。
上一篇：
Zookeeper集群安装
请登录后发表评论
登录
全部评论
