JZ-10矩形覆寫

【題目描述】

我們可以用2×1的小矩形橫着或者豎着去覆寫更大的矩形。請問用n個2×1的小矩形無重疊地覆寫一個2×n的大矩形，總共有多少種方法？

eg:

比如n=3時，23的矩形塊有3種覆寫方法：

【解法】

n=1

n=2

n=3

n=4

如果到這裡，還沒有發現規律怎麼辦呢？

那我們就再分析以下，從n=3到n=4，怎麼來的呢？

這裡有2種情況：

直接在n=3的情況下，再後面中添加一個豎着的。這個很顯然成立，有3種情況

然後橫着的顯然能添加到n-2的情況上，也就是在n=2後面，添加2個橫着的。有2種情況

通過以上分析，發現剛好和圖中的個數一樣。

是以總結：f [n]表示2n大矩陣 的方法數。

可以得出：f[n] = f[n-1] + f[n-2]，初始條件f[1] = 1, f[2] =2

是以代碼可用遞歸，記憶遞歸，和動态規劃和遞推

這裡隻寫遞推代碼：

int rectCover(int n) {
    if (n==0 || n==1 || n==2) return n;
    int a = 1, b = 2, c;
    for (int i=3; i<=n; ++i) {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}
           

**總結:**JZ7、8、9、10都是一類題。