题解 | #矩形覆盖#

题目难度：中等
考察内容：递推，dp，记忆化搜索
题目内容：我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2n的大矩形，从同一个方向看总共有多少种不同的方法？
*题目分析：**
一个12的矩形只有两种放的方式，横着和竖着，如果一个小矩形横着放，一定是两个矩形一起横着放

显然黄色的矩形没有其他放法了，也就是说最后一排只有两种放置情况

对于情况1，f[n-1]列已经是确定的了，所以f[n]+=f[n-2]
对于情况2，f[n]+=f[n-1]
所以f[n]=f[n-1]+f[n-2]
惊奇的发现，这是一个斐波那契数列，容易计算f[1]=1,f[2]=2
于是有三种解法如下，或者参考斐波那契数列
*算法1**（递归）
代码如下

class Solution {
public:
    int Fibonacci(int n) {
        if(n==2)return 2;//f[2]=2
        if(n==1)return 1;//f[1]=1
        //终止条件
          return Fibonacci(n-1)+Fibonacci(n-2);//f[n]=f[n-1]+f[n-2]
    }
};

复杂度分析：时间复杂度，每次调用f[n-1],f[n-2]所以时间复杂度为O(2^n)
空间复杂度，没有额外空间，空间复杂度O(1)
可以发现时间复杂度太高
算法2（记忆化搜索）
可以发现有很多值是重复调用的，浪费了大量时间,可以记录每次的值，下次再碰到可以直接O(1)查询
代码如下

class Solution {
public:

    int f[40]={0};
    int Fibonacci(int n) {
        if(f[n])return f[n];
        //如果f[n]已经求出了，直接调用即可
        if(n==1)return 1;//f[1]=1
        if(n==2)return 2;//f[2]=2
        //终止条件
          f[n]=Fibonacci(n-1)+Fibonacci(n-2);//f[n]=f[n-1]+f[n-2]
        return f[n];
    }
};

复杂度分析：时间复杂度，f[i]只会搜索一次，所以时间复杂度为O(n)
空间复杂度，有额外空间记录f[i]，空间复杂度O(n)
空间复杂度达到了O(n)
继续优化
算法3(递推)
反向考虑，我们知道了f0,f1,所以f2=f0+f1,我们知道了f2,所以f3=f2+f1。。。发现可以直接递推，但是空间复杂度还是O(n)的，每次只用到了两个变量fi-1,fi-2，所以可以只设置两个变量a,b,ans=a+b,然后递推，a=b,b=ans.
代码如下

class Solution {
public:
    int Fibonacci(int n) {
            long long a=1,b=2,ans=1;
            //a表示f[i-2],b表示f[i-1]
        if(n==0)return 0;
            //特判0
        for(int i=3;i<=n;i++)
            ans=a+b,a=b,b=ans;
            //f[n]=a+b,f[i-2]=b,f[i-1]=ans
        return ans;
    }
};
**复杂度分析：**时间复杂度，f[i]只会搜索一次，所以时间复杂度为O(n)
             **空间复杂度**，没有额外空间，空间复杂度O(1)