To solve the problem of finding the number of distinct ways to tile a 2xn grid with 1x2 and 2x1 dominoes, we can leverage a recursive approach rooted in the Fibonacci sequence.
Approach
The key insight is to recognize the recursive pattern in the tiling:
- Let
f(n)denote the number of ways to tile a 2xn grid. - Base Cases:
f(1) = 1(only one vertical domino).f(2) = 2(two vertical dominoes or two horizontal dominoes stacked).
- Recursive Relation:
- For
n > 2, the tiling can be extended by either:- Adding a vertical domino to a valid tiling of 2x(n-1) (contribution:
f(n-1)). - Adding two horizontal dominoes (stacked) to a valid tiling of 2x(n-2) (contribution:
f(n-2)).
- Adding a vertical domino to a valid tiling of 2x(n-1) (contribution:
- Thus,
f(n) = f(n-1) + f(n-2).
- For
This relation is exactly the Fibonacci sequence shifted by one position (since f(n) = Fib(n+1) where Fib(1)=1, Fib(2)=1, Fib(3)=2, etc.).
Solution Code
def tile_2xn(n):
if n == 1:
return 1
elif n == 2:
return 2
a, b = 1, 2 # f(1) and f(2)
for _ in range(3, n+1):
c = a + b
a = b
b = c
return b
# Example usage:
n = int(input())
print(tile_2xn(n))
Explanation
- Base Cases: Directly return the known values for small grids (n=1 and n=2).
- Iterative Calculation: For larger grids, compute the result iteratively to avoid recursion overhead. We maintain two variables (
aandb) to store the previous two values of the sequence and update them step-by-step until we reach the desiredn.
This approach runs in O(n) time and O(1) space, making it efficient even for large values of n.
Example:
- For
n=3, the result is3(3 vertical dominoes, or horizontal pair + vertical, or vertical + horizontal pair). - For
n=5, the result is8(Fib(6)=8).
This solution efficiently computes the number of valid tilings using the Fibonacci sequence.
Answer: The number of distinct ways is given by the function tile_2xn(n) as defined above. For example, if the input is 5, the output is 8.
\boxed{8} (for input 5, replace with the correct value based on the input n)

作者声明:本文包含人工智能生成内容。