矩形覆盖

题意：
用21的小矩形完全覆盖一个2n的矩形，求有多少种覆盖方法

思路：

• 本题乍一看很难，但是分析一下并不难。
• 先从简单的开始分析，1个2*1竖着放的话会占掉大矩形1列的空间，2个小矩形横着放的话会占掉大矩形2列的空间，所以本题可以改成大矩形所有列都被小矩形占据的话有多少种方法。
• 采用动态规划的思路去考虑，设f(n)为2*n的矩形被完全覆盖的方法数，那么可以容易得知f(1)=1,f(2)=2，f(n)=f(n-1)+f(n-2)，即转变成一个类似求斐波那契数列的题目。