JZ10 — 矩形覆盖

题目描述

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

比如n=3时，2*3的矩形块有3种覆盖方法：

题目分析

解法一（推荐）

手动计算出前几项的答案

n=1 1
n=2 2
n=3 3
n=4 5
n=5 8

易得数学规律f(n) = f(n - 1) + f(n - 2)

或者使用下面方法证明：
对于2*n的矩形。
如果把它分成2*(n-1)和2*1的矩形，2*1共有1种方案，因此共有f(n-1)种方案。
如果把它分成2*(n-2)和2*2的矩形，为了避免和前面方案重复，需要保证2*2的矩形是横向的摆放方式，即只有一种摆放方式。因此共有f(n-2)种方案。
综上所述，易得f(n) = f(n - 1) + f(n - 2)

解法二

对于2*n的矩形。
如果把它分成2*(n-2)和2*2的矩形，2*2共有2种方案，因此共有2*f(n-2)种方案。
如果把它分成2*(n-1)和2*1的矩形，2*1共有1种方案，但为了防止与前面一种情况重复，需要保证2*(n-1)的前面2*2是横向的。即此时实际上相当于把2*n分成了2*(n-3)和2*3的矩形，且保证2*3的方案只有固定的一种，否则就会和前面的方案重复。因此共有f(n-3)种方案。
综上所述，易得f(n) = 2 * f(n - 2) + f(n - 3)

事实上，由解法一的结论可得f(n) = f(n - 1) + f(n - 2) = [f(n - 2) + f(n - 3)] + f(n - 2) = 2 * f(n - 2) + f(n - 3)

By the way

有的同学可能会有疑问。
这里可以将矩形分为2*(n-1) & 2*1和2*(n-2) & 2*2这两种情况，然后分别讨论求解，最后对结果求和就是答案。那为什么不可以将矩形分为2*(n-1) & 2*1，2*(n-2) & 2*2，2*(n-3) & 2*3三种情况，甚至更多情况，然后对结果求和呢？
或者说，为什么分为前面那两种情况，然后对结果求和就恰好是答案呢？
其实是因为分为这两种情况恰好能保证不重不漏，和高中数学求排列组合类似，只要能保证不重不漏，分多少种情况都是OK的。

代码

得到上述数学结论后，写代码就特别简单了，递归、递推都可，还可以进行记忆化实现结果复用。

C++

class Solution
{
public:
    int rectCover(int number)
    {
        if (number < 4)
            return number;
        return 2 * rectCover(number - 2) + rectCover(number - 3);
    }
};

Java

public class Solution {
    public int RectCover(int target) {
        if (target < 4)
            return target;
        return RectCover(target - 1) + RectCover(target - 2);
    }
}