剑指offer——矩形覆盖问题

题目描述

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

思路一：

深度优先搜索，从（0,0）开始遍历，判断此格子情况，判断能否竖着放、横着放，把所有情况试探一遍。

class Solution {
public:
    int a[2][100];
    int rectCover(int number) {
        for(int i=0;i<100;i++){
            a[0][i]=0;
            a[1][i]=0;
        }
        int res=0;
        dfs(number,0,0,res);
        return res;
    }
    void dfs(int n,int x,int y,int &res){
        if(x==1 && y>=n-1){ //全部铺满了 此处y>=n-1与y>n-1等价  因为没有只剩下一个格子的情况
            res++;
            return;         //一定要return
        }
        if(a[x][y]==1)      //此格子已经铺了
        {
            dfs(n,x,y+1,res);
            return;         //一定要return

        }
        if(y>=n)            //该铺下一行了 不用判断x 因为第一个if语句过滤了x==1的情况
        {
            dfs(n,1,0,res);
            return;         //一定要return
        }
        //先考虑竖着铺
        if(x==0){
            a[0][y]=1;
            a[1][y]=1;
            dfs(n,x,y+1,res);
            a[0][y]=0;      //记住要回溯哦
            a[1][y]=0;      //记住要回溯哦
        }
        //判断能不能横着铺
        if(y+1<n){
            a[x][y]=1;
            a[x][y+1]=1;
            dfs(n,x,y+2,res);
            a[x][y]=0;      //记住要回溯哦
            a[x][y+1]=0;    //记住要回溯哦
        }   
    }
};

思路二：

递归或者动态规划

格子列数  1   2   n

排法数量  1   2   ?

格子列数到排法数量的映射关系记为F

当格子列数大于2时，我们这样把问题拆解：F(n)=F(n-1)+F(n-2)

把排列问题分两类，每类分两步：

       类一  ①(0,0)位置横着放一个，那么(1,0)位置必然也要横着放

                ②已经覆盖了 2×2的区域，2×(n-2)的区域覆盖方法有F(n-2)个

       类二  ①(0,0)位置竖着放一个

                ②已经覆盖了 2×1的区域，2×(n-1)的区域覆盖方法有F(n-1)个

分类相乘，分步相加， 结果为  1×F(n-1) + 1×F(n-2) 

同时结果集也是一个斐波那契数列

class Solution {
public:
    int rectCover(int number) {
        if(number<=2)return number;
        int a=1;
        int b=2;
        int res;
        for(int i=3;i<=number;i++){
            res=a+b;
            a=b;
            b=res;
        }
        return res;
    }
};

总结：方法二是时间复杂度与空间复杂度均远小于方法一，方法一被完爆