题解 | #矩形覆盖#

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

其实这道题没有什么代码难度，主要是思考过程。我们在排列矩形时按照如下规律即可：
在 n-1个小矩形的所有排列方式中，只在其右边添加一块竖着放置的矩形
在 n-2个小矩形的所有排列方式中，只在其右边添加两块横着叠加放置的矩形
在这样的排列中，所有排列方式均不重复，故问题简化为一个斐波那契数列，问题得以解决。
时间复杂度 O(n)
空间复杂度 O(1)

public class Solution {
    public int rectCover(int target) {
        int m = 1;
        int n = 2;
        int result = 2;
        if(target == 0 || target == 1){
            return target;
        }
        for(int i=2; i<target; i++){
            result = m+n;
            m = n;
            n = result;
        }
        return result;
    }
}