题目描述：在2×n的一个长方形方格中，用一个1×2的骨牌铺满方格，输入n，输出铺放方案的总数。

这是一道经典的动态规划问题，可以使用动态规划来解决。

定义状态：设f[i]表示2×i的长方形方格中铺放方案的总数。

状态转移方程：对于第i列，可以竖着放一块1×2的骨牌，或者横着放两块1×1的骨牌。如果竖着放一块骨牌，那么第i-1列必须也竖着放一块骨牌，此时方案数为f[i-2]；如果横着放两块骨牌，那么第i-1列必须也是横着放两块骨牌，此时方案数为f[i-2]；如果第i列不放骨牌，那么方案数为f[i-1]。因此，状态转移方程为：f[i] = f[i-1] + f[i-2]。

边界条件：f[1]=1，f[2]=2。

最终答案为f[n]。

下面是Python代码实现：

def tilingRectangle(n: int) -> int:
    if n == 1:
        return 1
    if n == 2:
        return 2
    f = [1, 2]
    for i in range(3, n + 1):
        f.append(f[-1] + f[-2])
    return f[-1]

时间复杂度为O(n)，空间复杂度为O(n)。

相关问题

在2×n的一个长方形方格中,用一个1× 2的骨牌铺满方格,输入n ,输出铺放方案的总数. 例如n=3时,为2× 3方格，骨牌的铺放方案有三种,如下图：

题目描述：在2×n的一个长方形方格中，用一个1×2的骨牌铺满方格，输入n，输出铺放方案的总数。

解题思路：这是一道典型的动态规划问题。我们可以用f(n)表示铺满2×n方格的方案数。对于第一列，我们可以竖着放一块骨牌，这样就剩下2×(n-1)的方格需要铺满，方案数为f(n-1)；或者横着放两块骨牌，这样就剩下2×(n-2)的方格需要铺满，方案数为f(n-2)。因此，f(n)=f(n-1)+f(n-2)。

代码实现：

有 2*n 的一个长方形方格，用一个 1 * 2 的骨牌铺满方格

题目描述：在2×n的一个长方形方格中，用一个1×2的骨牌铺满方格，输入n，输出铺放方案的总数。

解题思路：这是一道典型的动态规划问题。我们可以用f(n)表示铺满2×n方格的方案数。对于第一列，我们可以竖着放一块骨牌，这样就剩下2×(n-1)的方格需要铺满，方案数为f(n-1)；或者横着放两块骨牌，这样就剩下2×(n-2)的方格需要铺满，方案数为f(n-2)。因此，f(n)=f(n-1)+f(n-2)。

代码实现：