矩形覆盖

题目来源：牛客网--矩形覆盖

题目描述

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

解题思路

这又是一个斐波那契数列的变种，可以画个图找一下规律，会发现是符合下面这个规律的
fn = f(n-1) + f(n-2)

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