algorithm - 查找 Domino Tiling 的重复项

Question

我正在尝试解决 this spoj 上的问题。通过使用此教程中的 Link我能够弄清楚这种重复。

*****    AA***    AA***    AA***    A****
***** =  AA***  + A****  + AA***  + A****
*****    AA***    A****    A****    AA***
*****    AA***    AA***    A****    AA***

f(n)  =  f(n-2) + h(n-1) + g(n-1) + g(n-1).

但我不明白如何解决 h(n-1) 和 g(n-1) 的递归问题。

Answer 1

您需要边的所有 16 种可能轮廓的递归关系:

##
##
##
##

#.
##
##
##

##
#.
##
##

...

##
#.
#.
#.

#.
#.
#.
#.

这里的#表示一个格子被多米诺骨牌占据，.表示一个空格子。

你可以用f(n,0)到f(n,15)来表示它们，这样递归关系就很容易写了。您甚至可以自动枚举这些配置文件并生成关系。或者，您可以通过注意对称性(就像您已经注意到两个 g 的对称性一样)手动将配置文件数量减少 2 倍，然后手动编写方程式。