YBTOJ:平鋪方案

題目大意

求用\(2\times1\)或者\(2\times2\)的地磚鋪滿\(2\times n\)的地磚的方案數

題目分析

我們設\(f(n)\)為鋪滿\(2\times n\)的地闆的方案數，則\(f(1)=1\),\(f(2)=3\)

開始遞推，首先确立遞推關系式：

當把一塊\(2\times1\)的地磚豎着放在最右邊時，f(n)有f(n-1)種可能

當把兩塊\(2\times1\)的地磚橫着疊在最右邊時，占據\(2\times2\)的位置時，f(n)又有f(n-2)種可能；

當把一塊\(2\times2\)的地磚放在最右邊時，f(n)又有f(n-2)種可能；

綜上，f(n)=\(f(n-1)+f(n-2)+f(n-2)\);(為什麼不寫成\(f(n)=f(n-1)+f(n-2)\times2\)？因為我不想寫高精乘哈哈哈哈）

考慮優化

假如對于每一個n都來一個遞推，那麼鐵定TLE

怎麼優化呢？

在輸入之前就把\(f(1)\)~\(f(250)\)全部遞推出來

輸入之後直接輸出就好啦！

時間複雜度大大降低

Code