用多米诺骨牌填满 2 x n 数组

Question

我要写方法：

public int domino(int num)

我有一个二维整数数组 2 x num 大小（2 行和 num 列）

我需要找出有多少种方法可以用多米诺积木填满棋盘

（每个多米诺骨牌填满 2 个相互接触但不是对角线的格子）

我应该使用递归来做到这一点，但是

我想也许有办法做到这一点：

return(some sort of combinatorics formula )

这个有公式吗？

谢谢

Answer 1

这可以通过简单的递归方法来完成。假设 T(n) 是可以填充 2 x n 板的方式数。

现在考虑最左上角的单元格。覆盖它的多米诺骨牌可以以 2 种可能的方式定向。

1) 水平 2) 垂直

在情况 1 中，由于该多米诺骨牌是水平的，因此下面的单元格也必须由水平多米诺骨牌填充。在此之后，剩下一个 2 x (n-2) 板，可以用 T(n-2) 种方式填充。

在第二种情况下，还有一个 2 x (n-1) 的棋盘可以用 T(n-1) 种方式填充。

所以填充 2 x n 板的方法总数是

T(n) = T(n-1) + T(n-2) 基本情况是 T(1) = 1，这很容易验证。

它基本上是 斐波那契递推 具有封闭形式的解决方案。