推荐

完整《剑指Offer》算法题解析系列请点击 👉 《剑指Offer》全解析 Java 版

题目描述

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

public class Solution {
    public int RectCover(int target) {

    }
}

思路：

1.  n = 1 时，大矩形 2*1 ，有 1 种方法。

2.  n = 2 时，大矩形 2*2 ，有 2 种方法。

3.  n = 3 时，大矩形 2*3
    第3级，横着覆盖，剩下了 1 级，有 1 种方法；
    第3级，竖着覆盖，剩下了 2 级，有 2 种方法；
    总共有 1 + 2 = 3 种覆盖方法。

4. n = 4 时，大矩形 2*4
    第4级，横着覆盖，剩下了 2 级，有 2 种方法；
    第4级，竖着覆盖，剩下了 3 级，有 3 种方法；
    总共有 2 + 3= 5 种覆盖方法。

           ... ...

n. n = n 时，大矩形 2*n
    第n级，横着覆盖，剩下了 n-2 级，有 f(n-2) 种方法；
    第n级，竖着覆盖，剩下了 n-1 级，有 f(n-1) 种方法；
    总共有 f(n-1) + f(n-2) = f(n) 种覆盖方法。

对！斐波那契数列！

经过小青蛙 跳台阶 和 变态跳台阶 之后，这题分析出规律后就不难了。

 

实现：

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

 

看完之后，如果还有什么不懂的，可以在评论区留言，会及时回答更新。

这里是猿兄，为你分享程序员的世界。

非常感谢各位大佬们能看到这里，如果觉得文章还不错的话， 求点赞👍 求关注💗 求分享👬求评论📝 这些对猿兄来说真的 非常有用！！！

注： 如果猿兄这篇博客有任何错误和建议，欢迎大家留言，不胜感激！