737. Domino Tiling
A mosaic artist covers a strip that is 2 tiles tall and n tiles wide, with no gaps and no overlaps. Two kinds of pieces are available: a 2x1 domino, which may be laid either flat or standing up, and an L-shaped tromino that covers three cells of a 2x2 block, in any of its four rotations.
Return the number of different complete coverings of the 2 x n strip. Two coverings are different if some pair of neighbouring cells is joined by a piece in one covering but not in the other. The count can be very large, so return it modulo 1000000007.
Aim for time O(n) and extra space O(n) or better.
Example 1
- Input:
- n = 6
- Output:
- 53
- Explanation:
The sequence 1, 1, 2, 5, 11, 24, 53 follows f(i) = 2*f(i-1) + f(i-3), so a 2 x 6 strip has 53 tilings.
Example 2
- Input:
- n = 4
- Output:
- 11
- Explanation:
Extending the sequence 1, 1, 2, 5 by 2*5 + 1 gives 11 tilings for a 2 x 4 strip.
Example 3
- Input:
- n = 8
- Output:
- 258
- Explanation:
Continuing the sequence 53, 117, 258 gives 258 tilings for width 8.
Constraints
1 ≤ n ≤ 1000
Return the answer modulo 1000000007.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(n)