題目連結: https://zerojudge.tw/ShowProblem?problemid=d253
# 內容
如果我們要用常見的長度為高度兩倍的磚塊建一道磚牆，並且牆的高度為兩個單位，根據牆的長度，我們可以建出不同數量的花樣。從圖一我們可以看出：
!()[https://zerojudge.tw/ShowImage?id=216]
寛度為 1 單位的牆只有一種花樣 — 就是讓磚塊直立。
長度為 2 的牆有 2 種花樣 — 兩個平躺的磚磈疊在一起以及兩個直立的磚塊併在一起。
長度為 3 的牆有三種花樣。
長度為 4 的牆你可以找出幾種花樣？那長度為 5 的牆呢？
問題
你的工作是要寫一個程式，給它牆的長度，它就算出這道牆可以有幾種花樣。
# 解題思路
這題的規律其實就是費氏數列。
令牆壁的長度為 n，n 若等於 1，就是 1 塊；n 若等於 2，就是 2 塊；n 若大於 2，則 n 長度的牆壁可由 n-1 長度的牆壁加一塊垂直的方塊以及由 n-2 長度的牆壁加兩塊平行的方塊而得到。
# 程式碼
#include<iostream> | |
using namespace std; | |
int main(){ | |
int dp[55] = {0,1,2}; | |
int n; | |
for( int i = 3 ; i <= 50 ; i++ ) | |
dp[i] = dp[i-1]+dp[i-2]; | |
while( cin>>n && n ) | |
cout<<dp[n]<<endl; | |
return 0; | |
} |
