主題

ZeroJudge - d038: 00900 - Brick Wall Patterns 解題心得

Not In My Back Yard | 2021-01-18 00:00:06

題目連結:


題目大意:
輸入有多列,每列給定一正整數(當輸入 0 時,代表輸入結束),代表著有一堵牆其高度為 2 單位、長為給定的正整數單位長。

現在有一種 2 單位高、 1 單位長的磚塊。試問有多少種堆砌該牆壁的方法數?如下圖所示。



範例輸入:
1
2
3
0


範例輸出:
1
2
3


解題思維:
延續昨天的題目之精神。

可以發現遞迴式為 F(n) = F(n - 1) + F(n - 2),其中 F(n) 代表著長度 n 的牆之堆砌方法數。值得注意的是,遞迴式跟費氏數列是一樣的,但是本題的前兩項(n = 1 、 n = 2)之方法數為 1 、 2。

至於求法可以參見這題




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
32 巴幣: 0

創作回應

更多創作