递推计数

用 1×2 和 2×2 两种规格的瓷砖（可以旋转，1×2 的瓷砖可以竖着放或横着放），铺满一个 2×n 的长方形，n 为正整数。请问当 n=6 时，一共有多少种不同的铺法？

本题的核心是建立递推关系。先考虑最左边一列或两列如何铺，然后转化为更小宽度的问题。我们把 f(n) 记为铺满 2×n 长方形的方法数。分析最左边的情况： - 如果最左边竖着放一块 1×2 的瓷砖，则剩下 2×(n-1) 的区域，有 f(n-1) 种方法。 - 如果最左边两列用两块横着的 1×2 瓷砖（上下各一块），则剩下 2×(n-2) 的区域，有 f(n-2) 种方法。 - 如果最左边两列用一块 2×2 的瓷砖，则剩下 2×(n-2) 的区域，也有 f(n-2) 种方法。 注意：两种“用两列”的情况是不同的铺法，所以总方法数为 f(n) = f(n-1) + 2×f(n-2)。

第 1 步：设 f(n) 表示铺满 2×n 长方形的方法总数。 第 2 步：求初始值。 - 当 n=1 时，只有一块 1×2 的瓷砖竖着放（横着放不下），所以 f(1)=1。 - 当 n=2 时，可以：①两块 1×2 都竖着放；②两块 1×2 都横着放（上下各一块）；③一块 2×2 瓷砖。共 3 种，所以 f(2)=3。 第 3 步：根据递推公式 f(n) = f(n-1) + 2×f(n-2) 依次计算： - f(3) = f(2) + 2×f(1) = 3 + 2×1 = 5 - f(4) = f(3) + 2×f(2) = 5 + 2×3 = 11 - f(5) = f(4) + 2×f(3) = 11 + 2×5 = 21 - f(6) = f(5) + 2×f(4) = 21 + 2×11 = 43 第 4 步：检查 n=3 是否合理：可以枚举出 5 种，与计算结果一致，所以递推正确。

43 种。

解决铺砖类递推问题，关键是“看最左边”怎么铺，把大问题拆成小问题。需要仔细区分不同铺法是否产生相同的剩余区域，以及是否有重复计数。先写出递推公式，再代入初始值计算，步步检查。