剑指offer格子覆盖

题目&＃xff1a;

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形&＃xff0c;总共有多少种方法&＃xff1f;

比如n&＃61;3时&＃xff0c;2*3的矩形块有3种覆盖方法&＃xff1a;

思路&＃xff1a;

这个题其实是青蛙跳格子问题换了叙述方法&＃xff0c;青蛙跳格子问题见&＃xff1a;https://blog.csdn.net/qq_22498427/article/details/104708687

小格子可以一次竖着放一个&＃xff0c;也可以横着放两个。因此就像 n 级台阶&＃xff0c;青蛙一次可以跳两级&＃xff0c;也可以跳一级。

class Solution:def rectCover(self, number):if number &＃61;&＃61; 0:return 0ans0 &＃61; 1ans1 &＃61; 1for i in range(2,number&＃43;1):temp &＃61; ans0 &＃43; ans1ans0 &＃61; ans1ans1 &＃61; tempreturn ans1