d038: 900 - Brick Wall Patterns

出處 http://zerojudge.tw/ShowProblem?problemid=d038

內容 ：

如果我們要用常見的長度為高度兩倍的磚塊建一道磚牆，並且牆的高度為兩個單位，根據牆的長度，我們可以建出不同數量的花樣。從圖一我們可以看出：

• • 寛度為 1 單位的牆只有一種花樣—就是讓磚塊直立。

  • 長度為 2 的牆有 2 種花樣—兩個平躺的磚磈疊在一起以及兩個直立的磚塊併在一起。

  • 長度為 3 的牆有三種花樣。

長度為 4 的牆你可以找出幾種花樣？那長度為 5 的牆呢？

問題

你的工作是要寫一個程式，給它牆的長度，它就算出這道牆可以有幾種花樣。

輸入說明 ：

你將程式會收到一連串的整數，一行一個，每個整數代表牆的長度。牆的最大長度為 50。

輸出說明 ：

對於每個輸入的牆長度，你要輸出這道牆的花樣數量，每個數字單獨一行。

範例輸入 ：

1

2

3

0

範例輸出 ：

1

2

3

提示 ：

背景知識： DP

DP

出處 ：

UVa ACM 900 (管理：snail)

解題策略

費氏數列