题解 | #矩形覆盖#

矩形覆盖

http://www.nowcoder.com/practice/72a5a919508a4251859fb2cfb987a0e6

解决这题的突破口是找到递推规律。
根据题目给出的条件,从水平方向看,可以知道,我们竖着摆放21矩形时,必须一次至少摆两个,而横着摆放时,则可以一次摆一个。
所以我们对2
n的大矩形,在第一次摆放时,有两种选择,要么摆放一个横着的小矩形,要么一次摆放两个竖着的小矩形。
这样就可以得到递推式f(n)=f(n-1)+f(n-2)。从而得知,本题的递归公式与斐波那契数列一致,属于斐波那契数列的变种。

在面对这种递推题目时,理清思路,找准递推公式是关键。

class Solution {
public:
    int rectCover(int number) {
        if(!number){
            return number;
        }
        else if(number == 1){
            return 1;
        }
        else if(number == 2){
            return 2;
        }
        return rectCover(number - 1) + rectCover(number - 2);
    }
};
全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 13:38
点赞 评论 收藏
分享
机械打工仔:我来告诉你原因,是因为sobb有在线简历,有些HR为了快会直接先看在线简历,初步感觉不合适就不会找你要详细的了
投了多少份简历才上岸
点赞 评论 收藏
分享
06-25 16:25
梧州学院 Java
愿汐_:项目介绍那么长,然而你做了啥就一句话?
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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