矩形覆盖（Java实现）

1、题目

2.解法（递归）

public class Solution {
          
   
    private int c1 = 1;
    private int c2 = -1;
    public int RectCover(int target) {
          
   
        if (target == 0) return 0;
        if (target <= 2) {
          
   
            return target;
        }
        return RectCover(target-1) + RectCover(target-2);
    }
}

时间复杂度O(2^n)，空间复杂度O（c），c是递归栈的调用次数

非递归解法（使用的是斐波那契数列一样的解法）

public class Solution {
          
   
    private int c1 = 1;
    private int c2 = -1;
    public int RectCover(int target) {
          
   
        int sum = 0;
        if (target == 1) sum = 1;
        if (target == 2) sum = 2;
        
        int f1 = 1, f2 = 2;
        
        for (int i = 3; i <= target; i++) {
          
   
            sum = f1 + f2;
            f1 = f2;
            f2 = sum;
            // O(n-2) + O(n-1)
        }
        return sum;
    } 
}

时间复杂度为O(n), 空间复杂度为O(1)

3、思路

1、矩形2*N是竖着放的，所以n=1的时候只有1种方法，n=2的时候有两种方法，接着n=3,它可以选择13或者22组合，即先走1步，还剩3步需要确定，或者先走2步还有2步需要确定，所以结果是O(3)+O(2) ,注意13和31种只考虑1种情况，因为值会有重复。 2、以后考虑这种题，从小到大考虑。