欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

剑指offer----矩形覆盖

程序员文章站 2022-04-03 16:53:53
...

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

剑指offer----矩形覆盖

//如上图所示,n大于3时,有两种可能,红色部分为已经使用小矩形覆盖的部分,
//蓝色部分为未使用小矩形覆盖的部分,两部分叠加即可
int rectCover(int number) {
        if(number==1)return 1;
        else if(number==2)return 2;
        else if(number==0)return 0;
        return rectCover(number-1)+rectCover(number-2);
    }
//非递归法,和跳台阶差不多,有两种可能,当n>3时,相加两种可能即可,
//和上面递归方法的图一样,只有那两种可能性。
int rectCover(int number) {
        if(number==1)return 1;
        else if(number==2)return 2;
        else if(number==0)return 0;
        vector<int> vec(number,0);
        vec[0]=1;
        vec[1]=2;
        for(int i=2;i<number;++i)
        {
            vec[i]=vec[i-2]+vec[i-1];
        }
        return vec[number-1];
    }
相关标签: 矩形覆盖