题库 – 王码在线编程

P11106 - 骨牌问题

算法入门统计题解讨论

通过次数48 提交次数82 内存限制 64MB 时间限制1秒

描述

有一个 $ 2 \times n $ 的长方形方格，需要用若干 $ 1 \times 2 $的骨牌（即覆盖 1 行 2 列或 2 行 1 列的矩形）恰好铺满整个方格。骨牌可以横放或竖放，但不能重叠或超出边界。

请计算铺满 $ 2 \times n $ 方格的不同铺法总数。

例如，$n=3$时，为$ 2 \times 3$方格，此时用`3`个$ 1 \times 2$的骨牌铺满方格，共有`3`种铺法，见图9.5-5。