题目描述

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

比如n=3时，2*3的矩形块有3种覆盖方法：

解题思路

矩形覆盖支持两种形式，横着或竖着。

当n=1时，只能竖着覆盖，f(1)=1;当n=2时，既可以横着覆盖，也可以竖着覆盖，f(2)=2;当n=3时，最后一款只能竖着，其他的覆盖方式为f(2)，即：f(3)=f(1)+f(2)当n=N时，只需要考虑最后一块如何覆盖即可，即第一块只能竖着，推导出：f(n) = f(n-1)+f(n-2)

因此，该题目与青蛙跳台阶一样，可以跳一层、也可以跳两层，实现方案有两种：递归实现和循环实现。

实现代码

1.递归实现：

public class Solution {     public int rectCover(int target) {        if(target == 0) return 0 ;        if(target == 1) return 1 ;        if(target == 2) return 2 ;      	return rectCover(target-1) + rectCover(target-2);    }}

2.循环实现

public class Solution {    public int rectCover(int target) {        if(target == 0) return 0 ;        int a = 1, b = 1;        for (int i = 1; i < target; i++) {            a = a + b;            b = a - b;        }        return a;    }

如果您喜欢这篇文章，辛苦留言、点赞、关注~~~

更多剑指Offer技术分享：

剑指Offer-JZ1：二维数组中的查找

剑指Offer-JZ4：重建二叉树

剑指Offer-JZ7：斐波那契数列（难度：简单）

剑指Offer-JZ55：链表中有环的入口节点