关于算法-数据结构:一周刷完剑指offer10矩形覆盖

矩形笼罩

1. 题目形容

咱们能够用2 1的小矩形横着或者竖着去笼罩更大的矩形。请问用n个2 1的小矩形无重叠地笼罩一个2*n的大矩形，总共有多少种办法？

2. 示例

比方n=3时，2*3的矩形块有3种笼罩办法：

3. 解题思路

还是找法则的一道题，归根结底还是 斐波那契数列

如果是n=1 -> 1种

如果是n=2 -> 2种

如果是n=3 -> 3种

如果是n=4 -> 5种

留神，这里Python应用递归办法也是不能通过的，超过运行所要求的的工夫

4. Java实现

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

    }
}

5. Python实现

# -*- coding:utf-8 -*-
class Solution:
    def rectCover(self, number):
        # write code here
        if number <= 0:
            return 0
        if number == 1:
            return 1
        if number == 2:
            return 2
        
        a, b = 1, 2
        for i in range(number-2):
            a, b = b, a+b
        return b

如果您感觉本文有用，请点个“在看”