的多米諾平鋪

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倍減少配置文件數量，以及手動編寫公式。