一、题目描述

JZ10矩形覆盖
题目大意：
我们可以用2 * 1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2 * 1的小矩形无重叠地覆盖一个2 * n的大矩形，从同一个方向看总共有多少种不同的方法？
注意审题: 无重叠,重同一个方向看

二、算法1（递归）

算法思路

1.总体思路：根据题意,我们可以假设从左往右看,由于题目给定的小矩形的数量,以及大矩形的形状,因此我们可以发现每次,我们只能有两次选择,要么竖着放一个,要么横着放两个
2.递归边界就是当小矩形用完时结束

代码实现（C++11）

class Solution {
public:
    int rectCover(int number) {
        if(number == 0) return 0;
        return dfs(number);
    }

    int dfs(int n){
        if(n == 0) return 1;    // 刚好用完,合法
        if(n < 0) return 0;    // 非法方案
        return dfs(n - 1) + dfs(n - 2);    // 尝试两种放法
    }
};

时间复杂度：O(2^n)
空间复杂度：O(2^n)

三、算法2（动态规划）

算法思路

1.总体思路：定义状态数组f,f[i]表示当小矩形数量为i时有多少种方法,根据题意,每次可以选择竖着放一个或者横着放两个,故易知状态转移方程:

代码实现（C++11）

class Solution {
public:
    int rectCover(int number) {
        int f[number + 1];
        f[0] = 0, f[1] = 1, f[2] = 2;
        for(int i = 3; i <= number; ++i)
            f[i] = f[i - 1] + f[i - 2];
        return f[number];
    }
};

时间复杂度：O(n)
空间复杂度：O(n)

空间复杂度优化

观察递推方程我们可以发现,每次f[i]的值只和f[i - 1]和f[i - 2]有关,因此我们可以用两个变量来表示,递推即可

代码实现（C++11）

class Solution {
public:
    int rectCover(int number) {
        if(number == 0) return 0;
        if(number == 1) return 1;
        int pre = 1, cur = 2;
        for(int i = 3; i <= number; ++i){
            int tmp = cur + pre;
            pre = cur;
            cur = tmp;
            }
        return cur;
    }
};

时间复杂度：O(n)
空间复杂度：O(1)

四、算法三（矩阵快速幂）

观察状态转移方程,我们可以发现它和斐波那契数列的定义是相同的,因此可以采用矩阵快速幂的方法来解决,详细解法参见斐波那契数列题解
时间复杂度：O(logn)
空间复杂度：O(1)