题解 | #矩形覆盖#

算法思想一：迭代

解题思路：

图示：

分析从n=3到n=4，有2种情况：
1、直接在n=3的情况下，再后面中添加一个竖着的。这个很显然成立，有3种情况
2、然后横着的显然能添加到n-2的情况上，也就是在n=2后面，添加2个横着的。有2种情况
总结以上规律发现 fn 表示覆盖矩形的方法数，则 fn(n) = fn(n-1) + fn(n-2)

因此可以想到采用迭代的方式计算：

1、初始化：a = 1, b = 2

2、循环计算：fn = a + b, a = b, b = fn

3、返回fn

代码展示：

Python版本

class Solution:
    def rectCover(self, number):
        # write code here
        # 特殊情况
        if number <= 2:
            return number
        # 初始化
        a = 1
        b = 2
        # 循环计算
        for i in range(3, number+1):
            fn = a + b
            a = b
            b = fn
        return fn

复杂度分析

时间复杂度 $O(N)$ ：N表示number，循环计算次数 $O(N)$

空间复杂度 $O(1)$ ：仅使用多个常数级变量空间

算法思想二：递归

解题思路：

由方法一可知： $fn(n) = fn(n-1) + fn(n-2)$

所以采用递归的方式计算fn(n)，将计算fn(n)分为两个步骤 fn(n-1) 和 fn(n-2)，然后依次往下递归计算

代码展示：

JAVA版本

public class Solution {
    public int rectCover(int target) {
        // 特殊情况
        if (target <= 2){
            return target;
        }else{
            // 递归
            return rectCover(target - 1) + rectCover(target - 2);
        }
    }
}

复杂度分析

时间复杂度 $O(N)$ ：N表示number，递归计算次数 $O(N)$

空间复杂度 $O(N)$ ：递归算法中使用了栈空间 $O(N)$