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

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