Time Limit: 2000/1000 MS (java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 50253 Accepted Submission(s): 24237

PRoblem Description

在2×n的一個(gè)長方形方格中,用一個(gè)1× 2的骨牌鋪滿方格,輸入n ,輸出鋪放方案的總數(shù). 例如n=3時(shí),為2× 3方格，骨牌的鋪放方案有三種,如下圖：

Input

輸入數(shù)據(jù)由多行組成，每行包含一個(gè)整數(shù)n,表示該測(cè)試實(shí)例的長方形方格的規(guī)格是2×n (0 < n < =5 0)。

Output

對(duì)于每個(gè)測(cè)試實(shí)例，請(qǐng)輸出鋪放方案的總數(shù)，每個(gè)實(shí)例的輸出占一行。

Sample Input

1 3 2

Sample Output

1 3 2

本題思路： 一開始用dfs做，結(jié)果自然的超時(shí)了。于是發(fā)現(xiàn)原來是個(gè)遞推題。 過程如下： 每當(dāng)增加一個(gè)空位時(shí)如果豎著放的話，方法為f[n-1]， 如果橫著放，就需要兩個(gè)，把第n-1和第n 個(gè)橫著放，方法為f[n-2] 所以遞推出公式f[n]=f[n-1]+f[n-2]