矩形覆盖(python)

一,问题
我们可以用2x1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2x1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?

比如n=3时,2*3的矩形块有3种覆盖方法:
矩形覆盖(python)

二,思路
对于n而言,能填满他的,只有两种,1或2
举个栗子,当n=4时
矩形覆盖(python)
矩形覆盖(python)
矩形覆盖(python)
矩形覆盖(python)
矩形覆盖(python)
我们只看长n
要填满n=4,需要5种填法
1,1,1,1
1,1,2
2,2
1,2,1
2,1,1

我们发现,这不就是青蛙跳台阶嘛
也就是斐波那契数列

三,上代码:
矩形覆盖(python)
这么写也是可以的,无非一个倒着遍历,一个正着遍历而已
矩形覆盖(python)