下面要给大家带来的实例，就是和矩形覆盖相关的内容，你知道应该如何去实现吗?下面一起来看一下相关题目和思路以及实现方式吧!
题目：
用2*1的小矩形横着或者是竖着去覆盖更大的矩形。
问：
用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，一共有多少种方法呢?
例：
n=3的时候，2*3的矩形块有三种覆盖的方式
思路1：
假设：n块矩形有f(n)种覆盖方法。
进行逆向分析，要完成最后的搭建就存在着两种可能。
1、情况等价于情形1中阴影部分的n-1块矩形有多少种覆盖方法，为f(n-1);
2、情况等价于情形2中阴影部分的n-2块矩形有多少种覆盖方法，为f(n-2);
所以，f(n) = f(n-1) + f(n-2)，还是一个斐波那契数列。。。。且f(1) = 1, f(2) = 2。
代码实现：
public class Solution {
public int RectCover(int target) {
if(target <= 0){
return 0;
}
if(target == 1){
return 1;
}
if(target == 2){
return 2;
}
int first = 1;
int second = 2;
int result = 0;
for(int i = 3; i <= target; i++){
result = first + second;
first = second;
second = result;
}
return result;
}
}思路2：
代码实现：
public class Solution {
public int RectCover(int target) {
if(target <= 1){
return 1;
}
if(target*2 == 2){
return 1;
}else if(target*2 == 4){
return 2;
}else{
return RectCover((target-1))+RectCover(target-2);
}
}
}思路3：
n<1的时候，很明显的，是不需要用2*1块覆盖的，按照题目提示应该返回0。
n=1的时候，只有1种情况存在着。
n=2的时候，存在着2种情况。
n=3的时候，明显感觉到假如没有章法，思维难度比之前上升了很多。
本质上n覆盖方法种类都是对n-1时的扩展
可以明确，n时一定有n-1时原来方式与2*1的方块结合。
也就是, f(n)=f(n-1) + ?(暂时无法判断)。
假如我们现在归纳n=4，那么应该是什么形式呢?
保持原来n=3的时候的内容，并扩展一个2*1方块，形式分别为 “| | | |”、“= | |”、“| = |”
新增加的2*1方块和临近的2*1方块组成2*2结构，之后可以变形为“=”。所以n=4在原来n=3的基础上增加了"| | ="、“= =”。
再看一下这多出来的2种形式，是不是只比n = 2多了“=”。
那么，这就是关键点了。
因为，只要2*1或1*2有相同的两个时，就会组成2*2形式，所以就又可以变形了。
所以，自然而然可以得出规律：f(n)=f(n-1)+f(n-2)，(n > 2)。
假如，看了这一套理论还存在疑惑。
那么你可以尝试将题目改成1*3方块覆盖3*n、1*4方块覆盖4*n。
相应的结论：
1、1*3方块覆盖3*n区域：f(n)=f(n-1)+f(n - 3)，(n > 3)
2、1*4方块覆盖4*n区域：f(n)=f(n-1)+f(n - 4)，(n > 4)
更一般的结论，假如用1*m的方块覆盖m*n区域，递推关系式为f(n)=f(n-1)+f(n-m)，(n>m)。
代码实现：
public class Solution {
public int RectCover(int target) {
if (target < 1) {
return 0;
} else if (target == 1 || target == 2) {
return target;
} else {
return RectCover(target-1) + RectCover(target-2);
}
}
}以上思路和实现仅供参考，你还想了解更多的实例吗?可以继续的关注奇Q工具网的java实例栏目来了解哦，更多的实例可以分享给大家。
推荐阅读：