矩形覆盖

1.题目:
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2n的大矩形,总共有多少种方法?
比如n=3时,2
3的矩形块有3种覆盖方法:
图片说明
2.思路
涂掉最后一级矩形的时候,是用什么方式完成的?

n = 1 的时候
    只能横着覆盖,一种
n = 2 的时候
    可以横着和竖着覆盖,两种
n = 3 的时候
    第三级横着覆盖,用了一级,剩下 n = 2,有两种覆盖方法
    第三季竖着覆盖,用了两级,剩下 n = 1,有一种覆盖方法
    总共有 3 种
n = 4 的时候
    第 4 级横着覆盖,用了一级,剩下 n = 3,有三种覆盖方法
    第 4 级竖着覆盖,用了两级,剩下 n = 2,有两种覆盖方法
    总共有 5 种方法
n = n 的时候
    第 n 级横着覆盖,用了一级,剩下 n = n - 1,所以关注第 n - 1 种有几种覆盖方法
    第 n 级竖着覆盖,用了两级,剩下 n = n - 2,所以关注第 n - 2 种有几种覆盖方法
    总和为两种情况的总和

从 n = 1 到 n = 4 的示意图如下:
图片说明
综上所述,f(1)=1;f(2)=2;f(n)=f(n-1)+f(n-2)

public class Solution {
    public int RectCover(int target) {
        if(target==0||target==1||target==2){
            return target;
        }
        int a=1;
        int b=2;
        int c=0;
        for(int i=3;i<=target;i++){
            c=a+b;
            a=b;
            b=c;
        }
        return c;
    }
}
全部评论

相关推荐

06-20 17:42
东华大学 Java
凉风落木楚山秋:要是在2015,你这简历还可以月入十万,可惜现在是2025,已经跟不上版本了
我的简历长这样
点赞 评论 收藏
分享
05-12 11:09
已编辑
门头沟学院 后端
已注销:没必要放这么多专业技能的描述。这些应该是默认已会的,写这么多行感觉在凑内容。项目这块感觉再包装包装吧,换个名字,虽然大家的项目基本都是网上套壳的,但是你这也太明显了。放一个业务项目,再放一个技术项目。技术项目,例如中间件的一些扩展和尝试。
简历中的项目经历要怎么写
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务