• 00009.矩形覆盖
  • 发布于 1个月前
  • 35 热度
    0 评论

题目描述

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


解题思路:依旧还是斐波那契数列问题

老办法,遇到就画图,观察规律。笔者脑子不是非常厉害。只能依靠画图找规律。


斐波那契数列的问题。可以很清楚得看出来n等于1,2,3的时候是特殊情况,从第4项开始呈现出斐波那契数列的特征。那很好办了。老样子,不用递归,就用单层的循环就可以。同时借助变量做到O(n)的时间效率才是最好的。

贴代码:

public class Solution {
    public int RectCover(int target) {
        //前三项特殊情况
        if(target < 4) {
            return target;
        }
        //借助单层for循环搞定 同时借助两变量 时间效率和空间效率都是最低
        int prePreNum = 2;
        int preNum = 3;
        int result = 0;
        for(int i = 4; i < target + 1; i++) {
            result = prePreNum + preNum;
            prePreNum = preNum;
            preNum = result;
        }
        return result;
    }
}


用户评论