题意
我们可以用 2 * 1
的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 2 * 1
的小矩形无重叠地覆盖一个 2 * n
的大矩形,总共有多少种方法?
样例
对于一个 2 * 3
的矩阵,返回 3
。
思路
当 n 为 1 时,也就是
2 * 1
的大矩阵,只有一种方法:当 n 为 2 时,也就是
2 * 2
的大矩阵,有两种方法:当 n 为 3 时,也就是
2 * 3
的大矩阵,有三种方法:当 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 | public class Solution { |