我们可以用 2 * 1
的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 2 * 1
的小矩形无重叠地覆盖一个 2 * n
的大矩形,总共有多少种方法?
对于一个 2 * 3
的矩阵,返回 3
。
2 * 1
的大矩阵,只有一种方法:
2 * 2
的大矩阵,有两种方法:
2 * 3
的大矩阵,有三种方法:
2 * 4
的大矩阵,应该有几种方法呢?
4.1 根据原来 n = 3 时的内容,向右扩展一个 2 * 1
的矩阵,即:||||
、=||
、|=|
。
4.2 根据原来 n = 2 是的内容,向右扩展一个 =
形状的矩阵,即:==
、||=
。
你可以自己推导下 n = 5 时的情况,也是同样的规律。
规律为: f(n) = f(n-1) + f(n-2) (n > 3)
public class Solution {
public int RectCover(int target) {
if (target < 3) {
return target;
}
return RectCover(target - 1) + RectCover(target - 2);
}
}