剑指offer - 矩形覆盖(Java实现)

题目链接：https://www.nowcoder.com/practice/72a5a919508a4251859fb2cfb987a0e6?tpId=13&&tqId=11163&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

  思路一：递归，首先我们可以知道，如果 n = 1，则只有一种方式，n = 2 只有两种方式，n > 3 时，n - 1 拼接一个 2 * 1 的结构就可以得到 n 的情况，n - 2 拼接一个 2 * 2 的结构也可以得到 n 的情况。所以我们可以递归的去计算 n 的情况，到达 n = 0, 1, 2 的情况我们就可以返回。

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

  思路二：递推，当 n = 0 时，返回 0 种，其他情况下为斐波那契数列。fib[i] = fib[i - 1] + fib[i - 2]

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