计算使用n个2*1的小矩形覆盖2*n的大矩形的覆盖方式有多少种

解此种题型，需要从计算的结果入手，即赋予假定值，然后罗列计算的结果，最后根据计算的结果推断出相关算法。 假定n=1时，共有1种覆盖方式；假定n=2时，共有2种覆盖方式；假定n=3时，共有3种覆盖方式；假定n=4时，共有5种覆盖方式；假定n=5时，共有8种覆盖方式，以此类推，将计算出的结果罗列出来，分别是1、2、3、5、8、13……，经过分析，该数列属于斐波那契数列，所以，总共有(n-1)+(n-2)种覆盖方式。 解析代码如下：

# 资源包\Code\chapter19\1932.py
# 使用递归方式
def rectCover(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    elif n == 2:
        return 2
    elif n == 3:
        return 3
    else:
        return rectCover(n - 1) + rectCover(n - 2)
# 假设当n=4时
result = rectCover(4)
# 输出结果为：5
print(result)
# 使用非递归方式
def rectCover(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    elif n == 2:
        return 2
    elif n == 3:
        return 3
    else:
        res = [0, 1, 2, 3]
        while len(res) <= n:
            res.append(res[-1] + res[-2])
        return res[n]
# 假设当n=5时
result = rectCover(6)
# 输出结果为：13
print(result)