矩阵覆盖

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

题意

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

样例

对于一个 2 * 3 的矩阵，返回 3。

思路

  1. 当 n 为 1 时，也就是 2 * 1 的大矩阵，只有一种方法：
    image_1boc1vv7u143q1t1i1t91gudchhp.png-1.2kB

  2. 当 n 为 2 时，也就是 2 * 2 的大矩阵，有两种方法：
    image_1boc2455nekmi0o1o6r1misvuh16.png-1.5kB
    image_1boc25s6qmirakj15g69ia1m8h20.png-1.5kB

  3. 当 n 为 3 时，也就是 2 * 3 的大矩阵，有三种方法：
    image_1boc28qrh1sjc6m518anqpd11to3d.png-1.8kB
    image_1boc2a9km11561m1a1i7npg8flq3q.png-1.7kB
    image_1boc2dekcgv18c6kkn1sqh3vk4k.png-2kB

  4. 当 n 为 4 时，也就是 2 * 4 的大矩阵，应该有几种方法呢？
    4.1 根据原来 n = 3 时的内容，向右扩展一个 2 * 1 的矩阵，即：||||、=||、|=|。
    4.2 根据原来 n = 2 是的内容，向右扩展一个 = 形状的矩阵，即：==、||=。

你可以自己推导下 n = 5 时的情况，也是同样的规律。

规律为： f(n) = f(n-1) + f(n-2) (n > 3)

代码实现

1
2
3
4
5
6
7
8
public class Solution {
    public int RectCover(int target) {
        if (target < 3) {
            return target;
        }
        return RectCover(target - 1) + RectCover(target - 2);
    }
}

原题地址

牛客网：矩阵覆盖