题解 | #矩形覆盖#

一.题目介绍
JZ10矩形覆盖
题目链接:https://www.nowcoder.com/practice/72a5a919508a4251859fb2cfb987a0e6?tpId=13&&tqId=11163&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
题目描述:我们可以用2x1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2x1的小矩形无重叠地覆盖一个2xn的大矩形，总共有多少种方法？
二.算法1(递归/分治)
当n==1时，有1种覆盖方法:

当n==2时，有2种覆盖方法:
;
当n==3时，有3种覆盖方法:

当n==4时，有5种覆盖方法:

从上述可以得到的递推关系式子:

利用上述递归式子可以写出代码

class Solution {
public:
    int rectCover(int number) {
        if(number < 1){
            return 0;
        }else if(number <= 2){
            return number;
        }else{
            return rectCover(number-1) + rectCover(number-2);//
        }
    }
};

时间复杂度:O(n * n) 其中n表示小矩形个数
空间复杂度:O(n)
优缺点:推导有难度,而且时间复杂度高，但是代码实现简单

三.算法2(记忆化递归)

动态规划的思想与算法1探讨的分治法相似，也是通过组合子问题的解从而得到整个问题的解。从上一个算法看得出来，分治分解出的子问题都是相对独立的，但是动态规划分解的子问题通常不是独立存在的。分治法有时候存在分解后的问题太多，因而重复计算也多的问题。那么如果能够保存已求得的子问题的答案，从而在再次使用的时候调出，就会节省大量的时间。我们可以用一个表（数组）来存放求得的子问题的解，这就是动态规划的思想。

class Solution {
public:
    int a[1000];
    int rectCover(int number) {
        if(a[number]!=0) return a[number];
        if(number<=0) return 0;
        if(number==1) {
            a[number]=1;
        } else if(number==2) {
            a[number]=2;
        }else{
            int p=rectCover(number-1);
            int q=rectCover(number-2);
            a[number]=p+q;
        }
        return a[number];
    }
};

时间复杂度:O(n)表示小矩形个数
空间复杂度:O(n)需要额外开辟一维数组来储存方案数
优缺点:利用数组对结果进行记录，时间复杂度降低，也很容易实现