JAVA算法:排布问题(Tiling Problem)
给定“2 x n”板和大小为“2 x 1”的瓷砖,计算使用2 x 1瓷砖平铺给定板的方法数。瓷砖可以水平放置,即1 x 2瓷砖,也可以垂直放置,即2 x 1瓷砖。
例如:
输入:3
输出:3
解释:我们需要3块瓷砖来铺2 x 3的木板。方法有:
- 将3块瓷砖垂直摆放,如图第一种黄色的铺设方案
- 将开始的2块瓷砖按照1 x 2的方式水平铺设,最后第3块瓷砖按照2 x 1的方式垂直铺设
- 将开始的第1块瓷砖垂直铺设;接下来的2块瓷砖按照2 x 1水平方式铺设
例如:
输入:4
输出:5
解释:
问题分析:
当 n=1 时:F(1) = 1
当 n=2 时:F(2) = 2