题解 | #矩形覆盖#

题目：https://www.nowcoder.com/practice/72a5a919508a4251859fb2cfb987a0e6

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param number int整型 
# @return int整型
#
class Solution:
    def rectCover(self , number: int) -> int:
        #当要覆盖2*n的大矩形的时候，可以分解成覆盖2*(n-1)的矩形+一个2*1的矩形（竖着），或者覆盖2*(n-2)的矩形+2个2*1的矩形（横着）
        #所以覆盖2*n的大矩形其实就是覆盖2*(n-1)的矩形与覆盖2*(n-2)的矩形方法数之和
        #因此递推公式就是f(n)=f(n-1)+f(n-2)，和斐波那契数列类似了
        #f(1)=1,f(2)=2,f(3)=3,f(4)=5
        #发现规律也就是f(n)=f(n-1)+f(n-2)
        if number<=2:
            return number
        else:
            a=1
            b=2
            for i in range(number-2):
                cusum=a+b#直接求和
                a=b#更新a
                b=cusum#更新b
            return cusum

题解区天霸不要WA的图解很形象。