算法题10.矩形覆盖

题目描述:

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

乍一看还没有什么头绪，不过去评论区逛了逛立马思路清奇：
分析问题：

1. 首先，当n < 1时，矩形太小或者输入非法，所以此时返回0，即f(n) = 0 (n <1)。

2. 其次，当n = 1时，很显然只有一种覆盖方法，即 f(1) = 1。

3. 接着，当n = 2时，有两种覆盖方法，横着两个或竖着两个，即 f(2) = 2。
   

   

4. 当n > 2时，我们可以将问题拆分一下，如图：

   • 先将第一列覆盖上一个矩形，那么剩下的就是一个2 * n-1的矩形，所以剩下区域的覆盖方法为f(n -1)种。
     
   • 或者将前两列覆盖上两个小矩形，那么剩下的就是一个2 * n-2的矩形，所以剩下区域的覆盖方法为f(n -2)种。
     
     注意这里可能会有小伙伴会疑惑为什么不竖着放去填充呢，因为这种情况在上一种情形中已经算过了啊，再算的就会算重的！
     
     综上，可得f(n) = f(n -1) + f(n-2) (n > 2)。
     

这不就是斐波那契数列吗！！，到了这里，我相信应该很好解决问题了吧，斐波那契的计算方法很多种，这里放上一个我看到的最优的一种解法：

public class Solution {

    /**
     * 当 n < 1 时，无法覆盖，所以f(n) = 0 (n< 1)
     * 当 n =1 时，只有一种覆盖方法,f(1) = 1
     * 当 n =2 时，有两种覆盖方法(横着两个或竖着两个),f(2) = 2
     * 当 n > 2时，f(n) = f(n-1) + f(n-2)
     */
    public int RectCover(int target) {

        if (target<1) return 0;

        int f0 = 0, f1 = 1;
        while (target-- != 0) {
            f1 += f0;
            f0 = f1 - f0;
        }
        return f1;
    }
}