的多米诺平铺

Question

发现复发，我使用的教程在此Link我能搞清楚这个复发试图解决this问题上spoj.By。

***** 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

你忘了在f复发的术语。

***** A**** AA*** AA*** AA*** A**** 
***** A**** BB*** B**** BB*** A**** 
***** B**** CC*** B**** C**** BB*** 
***** B**** DD*** CC*** C**** CC*** 
f(n) = f(n-1) + f(n-2) + h(n-1) + g(n-1) + g(n-1) 

以下是其他的再次发生。这个想法是找出所有可能的多米诺骨牌位置的最左边的列与未填充的正方形。

***** A**** AA*** 
***** A**** BB*** 
**** ****  **** 
**** ****  **** 
g(n) = f(n-1) + g(n-1) 

**** ****  **** 
***** A**** AA*** 
***** A**** BB*** 
**** ****  **** 
h(n) = f(n-1) + k(n-1) 

***** AA*** 
**** **** 
**** **** 
***** BB*** 
k(n) = h(n-1) 

Answer 2

您需要所有16个可能侧面型材递推关系：

## 
## 
## 
## 

#. 
## 
## 
## 

## 
#. 
## 
## 

... 

## 
#. 
#. 
#. 

#. 
#. 
#. 
#. 

这里#意味着.由多米诺占据一个单元格，空单元格。

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