To solve this problem, we need to determine the number of ways to tile a 2xn grid using 2x1 dominoes. This problem can be efficiently solved using dynamic programming based on the Fibonacci sequence.

Approach

The key insight here is recognizing the recurrence relation in the number of valid tilings:

1. For a 2x1 grid (n=1), there is exactly 1 way to tile it (a single vertical domino).
2. For a 2x2 grid (n=2), there are 2 ways (two vertical dominoes or two horizontal dominoes).
3. For any n > 2:
   • If we place a vertical domino at the end of the grid, the remaining part is a 2x(n-1) grid, which has f(n-1) ways to tile.
   • If we place two horizontal dominoes at the end (covering the last two columns), the remaining part is a 2x(n-2) grid, which has f(n-2) ways to tile.

Thus, the recurrence relation is: f(n) = f(n-1) + f(n-2).

Solution Code

n = int(input())
if n == 1:
    print(1)
elif n == 2:
    print(2)
else:
    a, b = 1, 2
    for _ in range(3, n+1):
        a, b = b, a + b
    print(b)

Explanation

• Initialization: We start with the base cases: a = f(1) = 1 and b = f(2) = 2.
• Iterative Calculation: For each n from 3 to the input value, we update a and b to b and a + b respectively. This avoids recursion and ensures we compute the result efficiently in O(n) time.
• Result: The final value of b gives the number of ways to tile the 2xn grid.

This approach is optimal and handles large values of n (up to the limits of integer precision in Python) without any issues. The time complexity is O(n) and the space complexity is O(1) since we only use a few variables.

Example:

• For n=3, the result is 3 (1+2).
• For n=4, the result is 5 (2+3).
• For n=5, the result is 8 (3+5).

This confirms the solution works correctly for the given problem.

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