矩形覆盖(思路和实现)

KLQ 2020-05-09 10:29:52 java常见问答 6145

下面要给大家带来的实例,就是和矩形覆盖相关的内容,你知道应该如何去实现吗?下面一起来看一下相关题目和思路以及实现方式吧!

题目:

用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实例栏目来了解哦,更多的实例可以分享给大家。

推荐阅读:

顺时针打印矩阵如何实现?思路和实现分享java

数组-构建乘积数组(思路和代码实现)

矩阵中的路径(Java代码实现附思路)