关于算法-数据结构:一周刷完剑指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

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