题解 | #矩形覆盖#

对于2n的大矩形，一共需要n块小矩形块
分析：
当放置第n块小矩形时，一共有两种放法，*要么横着放，要么竖着放**
当第n块小矩形竖着放时，情况如图所示

此时前面一共有f(n-1)种放法；
当第n块小矩形横着放时，情况如图所示

此时第n块与第n-1块必定是横着叠放
此时前面一共有f(n-2)种放法；
因此f(n) = f(n-1) + f(n-2);
而f(0) = 0, f(1) = 1, f(2) = 2.
因此代码如下

public int rectCover(int target) {
        //一共需要n块木板,放置第n块木板的时候,要么横着放,要么竖着放
        //如果是竖着放,前面的n-1就已经放满了,有f(n-1)种可能
        //如果是横着放,一定是两根一起横着放,前面n-2就已经放满了, 有f(n-2)种可能
        //所以f(n) = f(n-1) + f(n-2);
        if(target <=2){
            return target;
        }
        int a = 1;
        int b =2;
        for(int i = 3;i<=target;i++){
            b = a+b;
            a = b-a;
        }
        return b;
    }