[hdu-2045] 不容易系列之(3)—— LELE的RPG難題 不容易系列之(3)—— LELE的RPG難題

time limit: 2000/1000 ms (java/others)    memory limit: 65536/32768 k (java/others)

total submission(s): 28032    accepted submission(s): 11192

problem description

人稱“ac女之殺手”的超級偶像lele最近忽然玩起了深沉，這可急壞了衆多“cole”（lele的粉絲,即"可樂"）,經過多方打探，某資深cole終于知道了原因，原來，lele最近研究起了著名的rpg難題:

有排成一行的ｎ個方格，用紅(red)、粉(pink)、綠(green)三色塗每個格子，每格塗一色，要求任何相鄰的方格不能同色，且首尾兩格也不同色．求全部的滿足要求的塗法.

以上就是著名的rpg難題.

如果你是cole,我想你一定會想盡辦法幫助lele解決這個問題的;如果不是,看在衆多漂亮的痛不欲生的cole女的面子上,你也不會袖手旁觀吧?

input

輸入資料包含多個測試執行個體,每個測試執行個體占一行,由一個整數n組成，(0<n<=50)。

output

對于每個測試執行個體，請輸出全部的滿足要求的塗法，每個執行個體的輸出占一行。

sample input

sample output

分析：這是一個遞推問題

1、數組 nums [ n ] 儲存 n 個格子有多少種塗法。

2、n 個格子的塗法可以由 n - 1 個格子的塗法再加 1 個格子得到。n - 1 個格子塗好後，再加 1 個格子就隻能塗 1 種顔色，是以nums [ n ] = nums [ n - 1 ] * 1

3、由 n - 1 個格子遞推到 n 個格子的時候，會出現一個問題：原來 n - 1 個格子的首尾兩個格子不能同色，加 1 個格子後，原來的 n - 1 個格子的首尾兩個格子可以同色了！

4、在 n 個格子出現問題的基礎上，反推可知：n - 1 個格子首尾同色的時候，n - 2 個格子肯定合法！是以，n - 1 個格子首尾同色，再加 1 個格子就可以塗 2 種顔色，是以nums [ n ] = num [ n - 2 ] * 2

5、綜上所述：nums [ 1 ] = 3 ; nums [ 2 ] = 6 ; nums [ 3 ] = 6 ; nums [ n ] = nums [ n - 1 ] * 1 + nums [ n - 2 ] * 2