矩形覆盖

题目描述

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

分析：

对于2*n的目标矩形，我们在进行覆盖的时候，可以第一块竖着放，也可以第一块横着放。

• 第一块竖着放：剩下2*（n-1）的空间，可以继续考虑在剩下的空间中第一块竖放还是横放。
• 第一块横着放：此时，在这一块的下面必然有一个12的空间，也就意味着必须有一块砖也要横着放在它下面才能保证无重叠的覆盖。横放两块后，剩下的空间为2（n-2），此时可以任意放砖。
  即，f(n)=f(n-1)+f(n-2)
  由此可见，又是一个斐波那契数列的题目,那就复习一下前面写跳台阶学到的知识点呗。
  首先，递归，但是递归会产生大量的重复计算，效率低下，不建议使用。
  其次，根据地推公式用数组保存每一步的中间结果，最后返回需要的结果，时间复杂度O(N),空间复杂度O(N）
  改进，只使用两个变量（常数个变量）来保存中间的计算结果，这样时间复杂度为O(N),空间复杂度O(1)

代码：

时间复杂度O(N),空间复杂度O(N）

public class Solution {
    public int RectCover(int target) {
        if(target<=0) return 0;
        else if(target<=2) return target;
        int[] num = new int[target+1];
        num[0]=0;
        num[1]=1;
        num[2]=2;
        for(int i=3;i<target+1;i++){
            num[i]=num[i-1]+num[i-2];
        }
        return num[target];
    }
}

时间复杂度O(N),空间复杂度O(1)

public class Solution {
    public int RectCover(int target) {
        if(target<=0) return 0;
        else if(target<=2) return target;
        int result =0;
        int pre1=1;
        int pre2=2;
        for(int i=3;i<target+1;i++){
            result = pre1+pre2;
            pre1=pre2;
            pre2=result;
        }
        return result;
        
    }
}