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

 

思路: 这种题开始肯定要找规律, 看了看, n = 1时, 一种方法; n = 2时, 两种方法; n = 3时,三种方法; n = 4时, 五种方法; … ; 很自然想起了斐波那契数列。

证明一下: 

设 n 列一共有 f(n) 种无重叠的覆盖方法,先上一个自己画的图方便理解。

1、对于n > 2的情况:首先我们可以知道小矩形是2 * 1,整个矩形为2 * n,所以我们在填充的时候只有横着填充跟竖着填充。 所以思路就是将从第1列填充到第n列的情况分解.

怎么分解呢,然后我又画了下面这个图, 方便理解。

我想求从A到G总共多少中走法,咋求呢?   我先分解, 在第一步我有两种走法, 要么走B要么走C,然后B往后又有两种走法,C往后又有…

 

所以,说这么多,对于矩形填充所有情况, 那么先走第一步, 两种情况:竖着放或者横着放。 

(1)对于第一步竖着放:  直接占据一竖列就OK了, 然后还剩下 n-1 列, 而n-1 列有 f(n-1) 种填充方法, 所以第一步竖着放总共有 1 * f(n-1) = f(n-1) 种方法;

(2)对于第一步横着放:  先放一个 2 * 1 小矩形,让它占据第一行第一、二列, 此时还剩下 n-2 列加上一个第二行第一、二列的区域。 我们难以用科学的方法表示出来, 怎么办?那就继续分解。

对于第二行第一、二列的区域,我们只存在唯一方式就是横着放上小矩形, 这样操作之后还剩下 n-2 列有 f(n-2) 种填充方法, 所以第一步横着放总共有 1 * 1 * f(n-2) = f(n-2) 种方法。

那么好了, 将这两个合并就是n列一共的方法数了, 即 f(n-1) + f(n-2) = f(n) 。看到这个式子是不是很熟, 对, 斐波那契数列。

2、那好,现在考虑到 n = 2 的情况, 不用 f(n-1) + f(n-2) = f(n) 这个公式, 更不要直接穷举, 用1中的思想考虑,可以得到:  f(2) = 1 + 1 * 1 = 2 。

 

 

顺便想一下, 假如用 3 * 1 的小矩形填充 3 * n 的大矩形呢?

我们还是用 f(n) 表示 n 列的所有方法,第一步还是分两种情况:

(1)横着放:  横着放占了三列, 剩下 n-3 列, 总共情况为 1 * 1 * f(n-3) = f(n-3)

(2)竖着放: 竖着放了一列, 剩下 n-1 列, 总共情况为 1 * f(n-1) = f(n-1)

所以 f(n) = f(n-1) + f(n-3)

 

接下来还有其他变形都OK了。

版权声明:本文为purehol原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:http://www.cnblogs.com/purehol/p/8088184.html