解题思路(2×N 用 1×2 小板铺满)
这是经典的 2×n 骨牌覆盖 问题。每块地板是 1×2,可以横着放(占一行两列)或竖着放(占两行一列)。
设 dp[i] 表示铺满 2×i 大青板的方案数。
考虑最后一列/最后两列的摆放方式:
1. 最后一块竖放
竖着放一块 1×2(实际覆盖两行一列),就把问题变成铺满 2×(i-1):
* 贡献 dp[i-1]
2. 最后两块横放(上下各一块)
如果最后一列不是竖放,那为了铺满最后两列,只能在上下两行各横放一块,覆盖 2×2 的区域:
* 贡献 dp[i-2]
因此得到递推:
* dp[i] = dp[i-1] + dp[i-2]
初始条件:
* dp[1] = 1(2×1 只能竖放 1 种)
* dp[2] = 2(2×2:两块竖放,或两块横放)
答案输出 dp[n]。
(这就是斐波那契型递推,n ≤ 60 用 long long 足够。)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
C++ 代码