矩阵覆盖

题意

我们可以用 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);
}
}

原题地址

牛客网:矩阵覆盖

坚持原创技术分享,您的支持将鼓励我继续创作!