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