作者：翟天保Steven
版权声明：著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处
成都创新互联成立与2013年，先为敦化等服务建站，敦化等地企业，进行企业商务咨询服务。为敦化企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。题目描述：
我们可以用 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的博客-博客
该文章中提供了4种递优的解法，以帮助大家更好地理解动态规划。但该4种解法中最优解的时间复杂度也要O(n)，因此我又探究了如何实现O(logn)的解法，将问题转换为矩阵求解的形式，运用快速幂的方法实现了高次幂的快速求解，达到了O(logn)水平。参考文章如下：
剑指offer(C++)-JZ10：斐波那契数列(时间复杂度O(logn)解法)_翟天保Steven的博客-博客
以上两篇文章都是解决斐波那契数列问题的相关内容，希望能对你有一些帮助。
推荐电影——消失的她！
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
网页标题：剑指offer(C++)-JZ70：矩形覆盖-创新互联
本文路径：
http://cdkjz.cn/article/hghhe.html
