[劍指offer] 矩形覆寫

本文首發于我的個人部落格： 尾尾部落

題目描述

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

解題思路

依舊是斐波那契數列

f(1) = 1

f(2) = 2

當n=3時，它可以由n=2的情況再覆寫一塊得到，也可以由 n=1的情況再覆寫 2 塊得到，是以 f(3) = f(1) + f(2)，依次往下推，可以得到

f(n) = 1, (n=1)

f(n) = 2, (n=2)

f(n) = f(n-1) + f(n-2), (n>2)

用遞歸的方法即可實作

參考代碼

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