题目描述：
我们可以用 2*1 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 2*1 的小矩形无重叠地覆盖一个 2*n 的大矩形，从同一个方向看总共有多少种不同的方法？
数据范围：0≤n≤38
进阶：空间复杂度 O(1) ，时间复杂度O(n)
注意：约定 n == 0 时，输出 0
比如n=3时，2*3的矩形块有3种不同的覆盖方法(从同一个方向看)：
输入描述：
2*1的小矩形的总个数n
返回值描述：
覆盖一个2*n的大矩形总共有多少种不同的方法(从同一个方向看)
示例：
输入：
4
返回值：
5
解题思路：
本题是类似青蛙跳台阶的题目，本质上是一个数学问题。
假设2*(n)矩形的覆盖方案数量是f(n)，则2*(n)的大矩形有两种组合形式。2*(n-1)的大矩形加1块竖直的矩形是一种情况，2*(n-2)的大矩形加两块横放叠加的矩形是一种情况，所以f(n)=f(n-1)+f(n-2)，显然是斐波那契数列了，用动态规划的解法即可。
测试代码：
class Solution { public: int rectCover(int number) { // 当n为0、1、2时，可能的情况数量刚好和n一致 if(number <= 2) return number; // 初始化 int a = 1; int b = 2; int c = 0; // 斐波那契数列遍历 for(int i = 3; i <= number; ++i) { c = a + b; a = b; b = c; } return c; } };
常规跳台阶问题可以参考：
剑指offer(C++)-JZ69：跳台阶(算法-动态规划)_翟天保Steven的博客-CSDN博客
该文章中提供了4种递优的解法，以帮助大家更好地理解动态规划。但该4种解法中最优解的时间复杂度也要O(n)，因此我又探究了如何实现O(logn)的解法，将问题转换为矩阵求解的形式，运用快速幂的方法实现了高次幂的快速求解，达到了O(logn)水平。参考文章如下：
剑指offer(C++)-JZ10：斐波那契数列(时间复杂度O(logn)解法)_翟天保Steven的博客-CSDN博客
以上两篇文章都是解决斐波那契数列问题的相关内容，希望能对你有一些帮助。
