矩形覆蓋

題目描述
我們可以用 21 的小矩形橫著或者豎著去覆蓋更大的矩形。請問用 n 個(gè) 21 的小矩形無重疊地覆蓋一個(gè) 2*n 的大矩形，總共有多少種方法？

解題思路

public int RectCover(int n) {
    if (n < 2) return n;
    int[] dp = new int[n];
    dp[0] = 1;
    dp[1] = 2;
    for (int i = 2; i < n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n - 1];
}