[剑指offer] 矩形覆盖

题目描述

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

解题思路

依旧是斐波那契数列

f(1) = 1

f(2) = 2

当n=3时，它可以由n=2的情况再覆盖一块得到，也可以由 n=1的情况再覆盖 2 块得到，所以 f(3) = f(1) + f(2)，依次往下推，可以得到

f(n) = 1, (n=1)

f(n) = 2, (n=2)

f(n) = f(n-1) + f(n-2), (n>2)

用递归的方法即可实现

参考代码

public class Solution {
    public int RectCover(int target) {
        if(target<=0){
            return 0;
        }
        else if(target == 1|| target ==2){
            return target;
        }
        else{
            return RectCover(target-1) + RectCover(target-2);
        }
    }
}

• 上一篇
• 下一篇

版权属于: 尾尾部落

原文地址: https://cloud.tencent.com/developer/article/1327759

转载时必须以链接形式注明原始出处及本声明。

window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdMiniList":false,"bdPic":"","bdStyle":"1","bdSize":"24"},"share":{}};with(document)0[(getElementsByTagName('head')0||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];